[프로그래머스 코딩테스트 고득점 Kit] - 힙(heap)

프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)

더 맵게 - Level2

문제

문제에서 주어진 Operation을 한번 수행할 때 마다, 전체 음식의 수는 1개씩 줄어든다. 즉, 최대 $N$번 Operation을 수행한다.

scoville의 길이가 최대 $1,000,000$인 것을 고려한다면 , 매 Operation마다 $O(N)$ 의 탐색으로 최소 값을 찾는 것은 시간 초과인 것이 자명해보인다.

즉 $O(logN)$ 이하로 최솟 값을 찾아야 하는데, 이 때 쓰일 수 있는 자료구조가 Min-heap이다. Min-Heap의 특성 상 각각의 서브트리에 존재하는 루트노드가 항상 자식 노드보다 큰 것이 보장되고 최상위 루트 노드의 값이 전체 노드의 최솟값이므로 $O(1)$에 최소값을 찾을 수 있다. 이 후 해당 노드를 pop한 다음 Adjusting 하는데 최대 $O(logN)$의 시간이 소요되므로 매 Operation마다 $O(logN)$의 시간이 소요된다고 볼 수 있다.

Min-heap에서 pop되는 원소가 Heap에 존재하는 최소 원소이므로 해당 원소가 K이상일 떄 operation을 종료한다. N번의 Operation 이후에도 heap에 남아있는 원소가 K보다 작다면 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우이므로 -1을 리턴하는 방식으로 처리해준다면 문제를 해결할 수 있다.

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> PQ;
    for(auto item: scoville)
        PQ.push(item);

    while(PQ.size() > 1 && PQ.top() < K){
        int a = PQ.top(); PQ.pop();
        int b = PQ.top(); PQ.pop();
        int newItem = a + b * 2;
        PQ.push(newItem);
        answer += 1;
    }
    answer = PQ.top() < K ? -1 : answer;
    return answer;
}

디스크 컨트롤러 - Level3

문제

현재 가능한 작업 중에서 어떠한 일을 하는 것이 전체 평균 소요시간을 줄일 수 있는가? 에 대한 생각이 필요하다.

현재 가능한 작업 $t_1t_2t_3$ 에 대하여 각각의 작업의 {시작시간, 끝난 시간}을 $(s_1,e_1), (s_2,e_2), (s_3, e_3)$ 로 가정하자. 또한 $t_1,t_2,t_3$ 는 해당 작업의 소요시간을 기준으로 오름차순 정렬되어 있다고 가정한다.

1. $t_1$ , $t_2$, $t_3$ 순서대로 일을 끝마친다고 하였을 때, 총 소요시간은 $t_1 + \alpha + t_2 + \beta + t_3 $ 가 된다.

2. $\alpha$ : $t_2$가 시작 가능한 시간 ~ $t_1$이 일을 끝마치는 시간

3. $\beta$ : $t_3$가 시작 가능한 시간 ~ $t_2$가 일을 끝마치는 시간

4. $t_1, t_2, t_3$는 상수항으로 볼 수 있으므로, $\alpha, \beta$를 줄이는 것이 핵심이라고 볼 수 있다.

5. 이를 일반화 하여, $t_{k-1}$번째 일이 끝마치는 시간을 최소화 하는 것이 문제의 최적해라는 것을 알 수 있다.

6. 일이 끝마치는 시간을 최소화 하기 위해서는 현재 가능한 작업 중에서 소요시간이 가장 작은 일을 선택하는 것이 해답이다.

이 외에도, 현재 가능한 작업이 아무 것도 없을 경우 이 후에 작업 중 가장 먼저 오는 작업을 수행해야하므로 적절한 처리를 통해 문제의 정답을 구할 수 있다.

#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> pii;
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<pii, vector<pii>, greater<pii>> PQ;

    for(auto job : jobs){
        int st = job[0], t = job[1];
        PQ.push({st, t});
    }
    int time = 0; // 현재 시간
    while(!PQ.empty()){
        vector<pii> v;
        while(!PQ.empty() && PQ.top().first <= time){
            v.push_back(PQ.top());
            PQ.pop();
        }
        // 현재 가능한 작업이 없을 때
        if(v.empty()){
            time = PQ.top().first;
        }
        else{
            int target=0, sz = v.size();
            for(int i=1; i<sz; i++){
                if(v[i].second < v[target].second)
                    target = i;
                else if(v[i].second == v[target].second && v[i].first < v[target].first)
                    target = i;
            }

            answer += (time - v[target].first); // 대기 시간 
            answer += v[target].second;
            time += v[target].second;

            for(int i=0; i<sz; i++){
                if(i == target) continue;
                PQ.push(v[i]);
            }
        }
    }

    return answer / jobs.size();
}

이중우선순위큐 - level3

문제

최댓값을 찾아 삭제하는 연산이 $O(logN)$시간에 이루어질 수 있도록 maxHeap을 구현한다.

최솟값을 찾아 삭제하는 연산이 $O(logN)$시간에 이루어질 수 있도록 minHeap을 구현한다.

원소를 삽입할 경우, minHeap과 maxHeap에 둘 다 삽입하되 동기화 issue에 대한 고려가 필요하다.

문제가 발생하는 부분은 아래와 같다.

1. maxHeap에서 원소를 삭제하였는데 해당 원소가 minHeap에서 삭제되지 않은 상태
2. minHeap에서 원소를 삭제하였는데 해당 원소가 maxHeap에서 삭제되지 않은 상태

해당 문제를 해결하기 위하여 삭제 대상이 되는 원소를 Heap-tree을 순회하며 찾기에는 시간 복잡도의 이점이 사라진다.

즉, 삭제 연산을 바로 수행하지 않고 2개의 Heap이 공유하는 counter값을 통하여 pop되는 원소가 유효한지?(즉, 이전에 삭제된 적이 없는지) 확인하는 과정을 통하여 시간복잡도의 이점을 유지하면서 동기화 issue를 해결할 수 있다.

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

vector<int> solution(vector<string> operations) {
    vector<int> answer(2);
    map<int, int> counter; // 두 개의 큐를 동기화 하기 위함
    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;

    for(const auto& oper : operations){
        if(oper[0] == 'I'){
            minHeap.push(stoi(oper.substr(2)));
            maxHeap.push(stoi(oper.substr(2)));
            counter[stoi(oper.substr(2))] += 1;
        }else if(oper == "D 1"){
            // 큐에서 최댓값을 삭제   
            while(!maxHeap.empty() && counter[maxHeap.top()] == 0) maxHeap.pop();
            if(maxHeap.empty()) continue;
            int elem = maxHeap.top(); maxHeap.pop();
            counter[elem] -= 1;
        }else if(oper == "D -1"){
            // 큐에서 최솟값을 삭제
            while(!minHeap.empty() && counter[minHeap.top()] == 0) minHeap.pop();
            if(minHeap.empty()) continue;
            int elem = minHeap.top(); minHeap.pop();
            counter[elem] -= 1;
        }
    }

    while(!maxHeap.empty() && counter[maxHeap.top()] == 0) maxHeap.pop();
    while(!minHeap.empty() && counter[minHeap.top()] == 0) minHeap.pop();
    int e1, e2;
    e1 = maxHeap.empty() ? 0 : maxHeap.top();
    e2 = minHeap.empty() ? 0 : minHeap.top();
    answer[0] = e1, answer[1] = e2;
    return answer;
}