프로그래머스 - 힙(더 맵게, 디스크 컨트롤러, 이중우선순위큐)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12117

👀문제이해 및 풀이방법

힙을 사용하는 문제들이다 , 우선순위 큐를 사용하면 되는데 compare구조체를 통해 우선순위를 얼마나 잘 관리할지가 핵심이 되겠다
sort와 반대방향으로 우선순위 정렬이 된다는 것을 기억하면서 코드를 보면 더 쉽게 알 수 있다.

📝코드

1 더 맵게

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct compare{
    bool operator()(int& a,int& b){
        return a>b;   
    }
};

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

2 디스크 컨트롤러

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct ready_compare{
    bool operator()(pair<int,int>& a,pair<int,int>& b){
        return a.second>b.second;
    }
};
struct job_compare{
    bool operator()(pair<int,int>& a,pair<int,int>& b){
        return a.first>b.first;
    }
};
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,ready_compare> r_pq;
    priority_queue<pair<int,int>,vector<pair<int,int>>,job_compare> j_pq;
    for(int i=0;i<jobs.size();i++)
        j_pq.push({jobs[i][0],jobs[i][1]});
    int cur_time=0,finish=0;
    bool mutex=false;
    pair<int,int> process;
    while(finish!=jobs.size()){
        while(!j_pq.empty()){
            if(j_pq.top().first==cur_time){
                r_pq.push(j_pq.top());
                j_pq.pop();
            }
            else
                break;
        }
        if(mutex&&cur_time==process.second){
            mutex=false;
            answer+=cur_time-process.first;
            finish++;
        }
        if(!mutex&&!r_pq.empty()){
            mutex=true;
            process={r_pq.top().first,cur_time+r_pq.top().second};
            r_pq.pop();
        }
        cur_time++;
    }
    return answer/jobs.size();
}

3 이중우선순위큐

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
struct compare{
    bool operator()(int& a,int& b){
        return a>b;
    }
};
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> max_heap;
    priority_queue<int,vector<int>,compare> min_heap;
    int cnt=0;
    int tmp;
    for(int i=0;i<operations.size();i++){
        if(operations[i][0]=='I'){
            tmp =stoi((operations[i].substr(2)));
            max_heap.push(tmp);
            min_heap.push(tmp);
            cnt ++;
        }
        else if(operations[i]=="D -1" && cnt){
            min_heap.pop();
            cnt--;
        }
        else if(operations[i]=="D 1" && cnt){
            max_heap.pop();
            cnt --;
        }
        if(!cnt){
            while(!max_heap.empty())
                max_heap.pop();
            while(!min_heap.empty())
                min_heap.pop();
        }
    }
    if(cnt){
        answer.push_back(max_heap.top());
        answer.push_back(min_heap.top());
    }
    else{
        answer = {0,0};
    }

    return answer;
}