priority queue와 vector의 최소값

vector 에서 최소값과 그 다음 최소값을 빼내어 계산하여 넣고를 반복하는 문제가 나왔다.

 

처음에는 vector를 deque에 넣어서 sort로 정렬하여 문제를 풀었다.

 

sort(deque.begin(), deque.end());

int less = deque.front();

deque.pop_front();

int less2 = deque.front();

deque.pop_front();

 

이 방식을 사용하니 실행시간이 너무 느리게 나와서 효율성 검사에서 전부 실패했다.

 

찾아보니 C++ 의 sort 는 퀵정렬 기반이여서 O(NlogN)의 시간복잡도를 가진다고 한다.

 

그래서 좀 더 빠른 방법을 찾다가 priority queue를 찾았다.

 

사실 학부때에도 priority queue는 써본 기억이 거의 없다.

 

 priority queue는 queue와 거의 동일한데, 선언시 우선순위를 지정하여 원하는 순서대로 빼낼 수 있다는 장점이 있다.

 

시간복잡도도 push, pop 을 할 때, O(logN) 의 복잡도를 가지니 sort와 priority queue 중 하나를 쓴다면 priority queue가 더 낫다.

 

그래서 vector를 priority queue에 넣고, greater 로 정렬하여 작은 원소부터 빼내었다.

 

vector<int> v;

priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.end());

 

int less = pq.top();

pq.pop();

int less2 = pq.top();

pq.pop();

 

처음에는 priority_queue에 vector의 원소를 어떻게 넣을까 하다가 while 로 돌려서 하나씩 넣었었다.

 

for(int i=0; i<v.size(); i++) pq.push(v[i]);

 

근데 알고보니 처음에 priority queue를 생성할 때, 생성변수로 시작과 끝을 넣으면 알아서 들어갔다.