[C++] Heap 모음 (Priority Queue)

42626 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

 

 

solution

1. priority_queue 에 오름차순으로 scoville 배열의 원소들을 push 한다.

1-1. 내림차순으로 push 하기 위해서 priority_queue<int, vector<int>, greater<int>> 를 사용하거나 원소에 -1을 곱해서 추가한다.

2. top -> pop -> top -> pop 를 통해서 낮은 원소 2개를 공식에 따라 섞고 push(first + second * -1) 를 한다.

2-1. 이때 맨 처음 top -> pop 과정을 거치고 pq가 empty가 되었는데도 first의 값이 K보다 작으면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없으므로 -1을 return한다.

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0;i < scoville.size();i++) {
        pq.push(scoville[i] * -1);
    }
    
    while(!pq.empty()) {
        int first = pq.top() * -1;
        pq.pop();
        
        if (pq.empty() && first < K) {
            answer = -1;
            break;
        }
        
        int second = pq.top() * -1;
        pq.pop();
        
        if (first >= K)
            break;
        
        answer++;
        pq.push((first + second * 2) * -1);
    }
    
    return answer;
}

 

커스텀한 compare 함수로 우선순위 큐를 정렬하고 싶다면 다음과 같이 사용

이때 priority_queue는 기본이 내림차순이므로 반대로 해야 오름차순이 됨

struct cmp {
    bool operator()(int n1, int n2) {
    	return n1 > n2;
    }
};

---

42627 디스크 컨트롤러

https://school.programmers.co.kr/learn/courses/30/lessons/42627

 

solution

1. priority_queue에 작업 소요 시간을 오름차순으로 정렬한다.

2. 시간을 0부터 탐색하면서 현재 시간보다 먼저 요청된 작업에 대해서 queue에 추가한다.

2-1. 이때 방문처리도 함께 해준다.

3. queue가 비어있다면 현재 시간에 요청된 작업이 없다는 뜻이므로 시간을 증가한다.

4. queue에 작업이 있다면 작업을 실행하고 q.pop을 한다.

 

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

using namespace std;

struct compare {
    bool operator()(pair<int, int> p1, pair<int, int> p2) {
        if (p1.second == p2.second)
            return p1.first > p2.first;

        return p1.second > p2.second;
    }    
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;
    vector<int> visited(jobs.size(), false);
    
    int now = 0, cnt = 0;
    while (cnt < jobs.size()) {
        for(int i = 0;i < jobs.size();i++) {
            if (!visited[i] && jobs[i][0] <= now) {
                q.push({jobs[i][0], jobs[i][1]});
                visited[i] = true;
            }
        }
        
        if (q.empty()) {
            now++;
            continue;
        }
        
        answer += (now - q.top().first) + q.top().second;
        now += q.top().second;
        cnt++;   
        q.pop();
    }
 
    return answer / jobs.size();
}

---

42628 이중 우선순위 큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

 

solution

1. 우선순위 큐를 가상의 오름차순, 내림차순 두개로 관리한다.

2. 우선순위 큐의 원소 개수를 세는 cnt로 가상의 오름차순, 내림차순 큐를 하나의 큐로 관리한다.

2-1. push, pop 연산을 반복하면서 cnt를 증가, 감소 시킨다

2-2. 이때 cnt가 0이 되면 모든 queue를 비운다.

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    int cnt = 0;
    priority_queue<int> maxq;
    priority_queue<int, vector<int>, greater<int>> minq;
    
    for(int i = 0;i < operations.size();i++) {
        if (cnt == 0) {
            while(!maxq.empty())
                maxq.pop();
            
            while(!minq.empty())
                minq.pop();
        }
        
        if (operations[i][0] == 'I') {
            int item = stoi(operations[i].substr(1, operations[i].size()));
            maxq.push(item);
            minq.push(item);
            cnt++;
        }
        
        else if (operations[i] == "D 1") {
            if (cnt == 0)
                continue;
            
            maxq.pop();
            cnt--;
        }
        
        else {
            if (cnt == 0)
                continue;
            
            minq.pop();
            cnt--;
        }
    }
    
    if (cnt == 0)
        answer = {0 ,0};
    else
        answer = {maxq.top(), minq.top()};
    
    return answer;
}