[C++] 프로그래머스 : 코딩테스트연습_힙

1. 더맵게

pq활용기본문제 + 예외생각

반복문을 더 깔끔하게 짤 수 있음

#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]); // for mean heap
    }
    
    int res = 0 , tmp = 0;
    bool canMake = false;
    
    while(1){
        if(-pq.top() >= K){
            canMake = true;
            break;
        }
        
        if(pq.size() <= 1)
            break;
        
        answer++;
        
        tmp = -pq.top();
        pq.pop();
        res = tmp + (-pq.top())*2;
        pq.pop();
        pq.push(-res);
    }
    
    if(!canMake)
        return -1;
    
    return answer;
}

 

2. 디스크 컨트롤러

1) job 처리 우선순위가 comp인 것

2) 다음 job의 후보가 (현재시각, job의 요청시각, job의 처리시간) 3가지에 따라 생긴다는 것을 구현하는 것

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

using namespace std;

struct comp{
    bool operator()(pair<int,int> a, pair<int,int> b){
        if(a.second == b.second)
            return a.first > b.first;
        return a.second > b.second;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0, t = 0, idx = 0;
    
    sort(jobs.begin(), jobs.end());
    priority_queue<pair<int,int>, vector<pair<int,int>>, comp> pq;
    
    while(idx<jobs.size() || !pq.empty()){
        
        while(idx<jobs.size() && jobs[idx][0] <= t){
            pq.push({jobs[idx][0], jobs[idx][1]});
            idx++;
        }
        
        if(!pq.empty()){ // 맨 앞 job만 처리해야 처리이후 시간으로 다음 job 선정가능
            t += pq.top().second;
            answer += (t-pq.top().first);
            pq.pop();
        }
        else{
            if(idx < jobs.size())
                t = jobs[idx][0];
        }
    }
    
    return answer/jobs.size();
}

 

3. 이중우선순위큐

cnt변수를 쓰지 않고 max_heap.size() && min_heap.size()로 하면 아래 주석처리된곳이 원인이 되어 실패한다. 왜일까

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

using namespace std;

struct comp {
    bool operator()(int a, int b){
        return a > b;
    }
};

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int, vector<int>, comp> min_heap;
    priority_queue<int> max_heap;
    int cnt = 0;
    
    for(int i=0; i<operations.size(); i++){
        
        if(operations[i][0]=='I'){
            min_heap.push(stoi(operations[i].substr(2)));
            max_heap.push(stoi(operations[i].substr(2)));
            cnt++;
        }
        else if(operations[i][0]=='D' && cnt>0){
            if(operations[i][2] == '1'){
                max_heap.pop();
                cnt--;
            }
            else{
                min_heap.pop();
                cnt--;
            }
        }
        
        if(cnt==0){ // min_heap.size()==0 || max_heap.size()==0 -> 실패
            while(!max_heap.empty()) max_heap.pop();
            while(!min_heap.empty()) min_heap.pop();
        }
    }
    
    if(cnt>0){
        answer.push_back(max_heap.top());
        answer.push_back(min_heap.top());
    }
    else{
        answer.push_back(0);
        answer.push_back(0);
    }
    
    return answer;
}