<Programmers> Heap_더 맵게, Priority queue 구현 c++

Google 아니고 Joogle·2021년 11월 22일
0

Programmers

목록 보기
2/22

priority queue

우선순위 큐는 순서대로 기다리고 있는 자료들을 저장하는 자료 구조 라는 점에서 큐와 비슷하지만, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다는 차이가 있다.

우선순위 큐는 이진 검색 트리보다 훨씬 단순한 구조로 구현할 수 있는데, 그중 대표적인 것이 heap 이라는 트리이다.

아래는 Heap의 루트가 가장 큰 값을 가지는 Max Heap 에서 insert와 delete를 수행하는 수도코드를 작성한 것이다.
(root의 index는 1이다)


이 문제에서는 가장 작은 값을 pop, push해야 하기 때문에 Min Heap을 구현해야 한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
 
    priority_queue<int, vector<int>, greater<int>> pq;
  
    int scovilleSize=scoville.size();
    for (int i=0; i<scovilleSize; i++) 
        pq.push(scoville[i]);

    int answer = 0;
 
    while (pq.size()>=2 && pq.top()<K) {
        int first=pq.top();
        pq.pop();
        int second=pq.top();
        pq.pop();
        pq.push(first+second*2);
        answer++;
    }
   
    if (pq.top()<K)
        return -1;
    return answer;
}

위 코드에서

priority_queue<int, vector<int>, greater<int>> pq;
int scovilleSize=scoville.size();
for (int i=0; i<scovilleSize; i++) 
      pq.push(scoville[i]);

아래와 같이 바꿀  있다.
                             
priority_queue<int, vector<int>, 
  greater<int>> pq (scoville.begin(), scoville.end());
profile
Backend 개발자 지망생

0개의 댓글