프로그래머스 알고리즘 고득점 Kit - 힙

힙 자료구조

- 완전 이진 트리

- min heap, max heap 존재함 (부모 자식 간의 대소 관계)

- 삽입은 O(log n), 힙 빌드 시 O(n)

 

C++로 구현

- 인덱스 접근 편하게 배열로 함

- insert, removeMin, siftdown(heapify) 함수 필요

int n = 0;
int heap[1000000];

void swap(int i, int j) {
    int tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
}
void insert(int x) {
    heap[n++] = x;
    int parent;
    for(int k=n-1; k>0; k=parent) {
        parent = (k-1)/2;
        if(heap[parent] <= heap[k]) return;
        else swap(parent, k);
    }
}
void siftdown(int k) {
    int j;
    while(k*2+1 < n) {
        j = (k*2+1 == n-1) ? k*2+1 : (heap[k*2+1] < heap[k*2+2]) ? k*2+1 : k*2+2;
        if(heap[k] <= heap[j]) return;
        swap(k,j);
        k = j;
    }
}
void deleteMin() {
    heap[0] = heap[--n];
    siftdown(0);
}

for(int i=0; i<scoville.size(); i++) {
    n++;
    heap[i] = scoville[i];
}
// build min heap
for(int i=n/2-1; i>=0; i--) siftdown(i);

 

C++ 우선순위 큐 이용해 힙 구현

- priority_queue<int, vector<int>, less<int>> 하면 max heap, priority_queue<int, vector<int>, greater<int>> 하면 min heap

- for(int sc : scoville) { pq.push(sc); } 이렇게 push 해줘서 초기화해도 됨

- 우선순위 큐는 내부적으로 힙 구조를 사용한다고 함 (시간복잡도 동일)

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    int answer = 0;
    while(pq.top() < K) {
        if(pq.size() == 1) return -1;
        int sc1 = pq.top(); pq.pop();
        int sc2 = pq.top(); pq.pop();
        pq.push(sc1+sc2*2);
        answer++;
    }
    return answer;
}

 

디스크 컨트롤러

- (작업 요청 시간, 작업 소요 시간)이 배열로 주어지고, single-tasking 처리기기라고 하자

- 작업 수행 중이 아닐 때는 제일 먼저(빨리) 요청한 작업부터 처리함

- 작업의 요청부터 종료까지 걸린 시간의 합을 최소로 만드는 경우의 평균값을 구해야 함

=> 일단 waitingJobs 우선순위 큐를 만들어 소요시간 기준으로 min heap을 구성함

=> 두 개의 시작 가능한 task가 있다고 할 때 짧은 task를 먼저 해야 소요시간 합이 작아지기 때문

=> 매번 실행할 task를 고르기 전에 curr_time 전에 요청 들어온 task들을 min heap으로 관리

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    sort(jobs.begin(), jobs.end()); // 시작 시간 기준 오름차순 정렬
    
    int total_time = 0, job_processed = 0, curr_time = 0;
    auto comp = [](pair<int,int> a, pair<int,int> b) { return a.second > b.second; };
    priority_queue <pair<int, int>, vector<pair<int,int>>, decltype(comp)> waitingJobs(comp); // 대기중인 작업, 소요시간 짧은 순으로 정렬
    auto it = jobs.begin(); // jobs 벡터 iterator
    
    while(job_processed < jobs.size()) {
        while(it != jobs.end() && (*it)[0] <= curr_time) {
            waitingJobs.push(make_pair((*it)[0],(*it)[1]));
            it++;
        }
        if(waitingJobs.empty()) {
            // 대기중인 job 없다면 가장 먼저 들어오는 job 바로 수행
            total_time += (*it)[1];
            curr_time = (*it)[0] + (*it)[1];
            it++;
        } else {
            // 대기중인 job 중 제일 적게 걸리는 job 수행
            pair<int, int> p = waitingJobs.top(); waitingJobs.pop();
            total_time += (curr_time - p.first) + p.second;
            curr_time += p.second;
        }
        job_processed++;
    }
    
    return total_time / jobs.size();
}

 

우선순위 큐 정렬 기준 사용자화

- 구조체나 람다 함수를 사용할 수 있음 (https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator)

auto comp = [](const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> waitingJobs(comp);

 

이중우선순위큐

- 큐에 주어진 숫자를 삽입하고, 큐에서 최댓값과 최솟값을 삭제하는 작업을 할 수 있어야 함

- max heap과 min heap을 준비하고, length를 관리, length=0이 되면 두 힙을 모두 비워주어야 의도치않은 동작 (이미 지워진 원소를 또 지우려고 하는) 방지 가능

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

vector<string> split(const string& str, char delim) {
    vector<string> tokens;
    istringstream iss(str);
    string token;
    
    while(getline(iss, token, delim)) {
        if(token.length()>0) tokens.push_back(token);
    }
    
    return tokens;
}

vector<int> solution(vector<string> operations) {
    priority_queue<int, vector<int>, greater<int>> min_heap;
    priority_queue<int, vector<int>, less<int>> max_heap;
    
    int len = 0;
    for(string op : operations) {
        vector<string> res = split(op, ' ');
        if(res[0].compare("I")==0) {
            min_heap.push(stoi(res[1]));
            max_heap.push(stoi(res[1]));
            len++;
        } else {
            if(len <=0) continue;
            if(stoi(res[1])==-1) min_heap.pop();
            else max_heap.pop();
            
            len--;
            if(len==0) {
                min_heap = priority_queue<int, vector<int>, greater<int>>();
                max_heap = priority_queue<int, vector<int>, less<int>>();
            }
        }
    }
    
    vector<int> ans;
    if(len<=0) {
        ans.push_back(0); ans.push_back(0);
    } else {
        ans.push_back(max_heap.top()); ans.push_back(min_heap.top());
    }
    return ans;
}

- 참고로 priority_queue에는 clear 함수가 없어서 priority_queue<int, vector<int>, greater<int>>() 이렇게 초기화 필요함

 

cf) multiset을 사용할 수도 있음!

- 중복 요소 허용 (중복 key 값 허용)

- 내부적으로 트리 기반 구조를 사용하여 요소들을 정렬된 상태로 유지/저장

- dq.erase(dq.begin()) , dq.erase(--dq.end()) 혹은 dq.erase(prev(dq.end()) 로 최댓값과 최솟값 삭제 가능

#include <vector>
#include <string>
#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    multiset<int> dq;
    
    for (string op : operations) {
        if (op[0] == 'I') {
            int num = stoi(op.substr(2));
            dq.insert(num);
        } else if (!dq.empty()) {
            if (op[2] == '1') {
                // 최댓값 삭제
                dq.erase(prev(dq.end()));
            } else {
                // 최솟값 삭제
                dq.erase(dq.begin());
            }
        }
    }
    
    if (dq.empty()) {
        return {0, 0};
    } else {
        return {*dq.rbegin(), *dq.begin()};
    }
}