백준 23883 알고리즘 수업 - 선택 정렬 3 C++

간단한 해설

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 

선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구해야한다.

 

그런데 K가 최대 50만이고 시간제한은 3초이니까 30억미만으로 연산을 실행한다고 생각하면 된다.

 

은근 널널하므로 그냥 하나씩 힙을 이용하여서 인덱스를 추적하는 방식으로 조절하면 된다.

 

 

힙을 이용하는 방법에는 여러 가지가 있는데, set, priority_queue, map, multiset, multimap이 있지만, N개의 서로 다른 양의 정수가 저장되어 있으므로 그냥 set을 골랐다.

답

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	set<pair<int,int>> s; // val, index
	int n,k;
	cin>>n>>k;
	vector<int> v(n);
	for(int i=0;i<n;++i){
		cin>>v[i];
		s.insert({-v[i],i});
	}
	int count=0;
	pair<int,int> ans={-1,-1};
	for(int i=n-1;i>=0;--i){
		int val=-s.begin()->first;
		int idx=s.begin()->second;
		if(v[i]!=val){
			++count;
			int tmpVal=v[i];
			s.erase({-v[i],i});
			s.erase({-val,idx});
			swap(v[i],v[idx]);
			s.insert({-tmpVal,idx});
			if(count==k){
				ans={min(v[idx],v[i]),max(v[idx],v[i])};
				break;
			}
		}
		else{
			s.erase({-v[i],i});
		}
	}
	if(ans.first==-1) cout<<-1;
	else{
		cout<<ans.first<<" "<<ans.second;
	}
}