[힙(Heap)] 더 맵게, 라면 공장, 이중 우선순위 큐

힙은 완전이진트리자료구조이다.

< 완전 이진 트리 >

완전 이진 트리는 다음과 같은 성격을 지닌다.

 

1. 이진 트리는 하나의 부모에 두개의 자식을 지닌다.

2. 값은 자식의 왼쪽부터 순서대로 입력받는다.

3. 부모는 자식보다 무조건 크거나 작고( 정렬 기준에 따라 다르다.) 고로 Root 노드는 가장 크거나 가장 작다.

 

이와 같이 힙 구조를 이용하면 완전히 정렬하지 않더라도, 최대값 혹은 최소값을 구할 수 있게 된다.

(일반적인 정렬은 nlogn의 시간만큼 드는 반면 힙은 깊이만큼만 실행하므로 logn만큼의 시간 복잡도가 생긴다.)

 

c++ 에서는 이와 같은 힙을 활용해서 만든 STL Container인 우선순위 큐가 있다.

우선순위 큐를 이용하면 모두 정렬하지 않아도 최대값 혹은 최소값을 하나씩 구할 수 있다.

 

우선순위 큐의 사용은 다음과 같다.

• 헤더 파일
  #include <queue>
•  선언
  priority_queue<T, Container, Compare> : 첫번째로 큐의 타입, 두 번째로는 Container ( 정확히 어떤 컨테이너인지 모르겠는데 일반적으로 vector<T>) 세번째로 Compare 타입을 선언해준다.
• 추가 및 삭제
  push(element) : 큐에 원소 추가 (이 때 기존의 값보다 크다면 맨 위로 입력)
  insert(element) : 큐에 원소 추가
  pop(element) : 우선순위 큐에 top의 원소 제거
• 조회
  top() : top에 있는 원소 반환
• 기타
  empty() : empty 여부
  size() : 크기를 int형으로 반환

더 맵게

< 문제 >

우선 순위 큐를 오름차순으로 생성해야 한다.

그렇기 때문에 compare 타입에는 greater<T>(첫번째 인자가 두번째 인자보다 크면 true)를 이용했다.

참고로 반대는 less<T>

#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> q;
    int answer = 0;
    for(int value : scoville) {
        q.push(value);
    }
    int min, min1, min2;
    while(q.top() < K) {
        if(q.size() == 1) {
            return -1;
        }
        min1 = q.top();
        q.pop();
        min2 = q.top();
        q.pop();
        min = min1+ min2 *2;
        q.push(min);
        answer++;
    }
    return answer;
}

< 코드 >

 

라면공장

< 문제 >

개인적으로 애먹은 문제

heap으로 분류되어 있지 않았다면 dp로 완전탐색했을 듯.

 

요점은

특정 구간에서의 값들을 최대값 순서대로 모두 기록해뒀다가

특정 경우에 그 값들 중 최대 값을 가져오는 식이다.

 

예시의 테스트 케이스 외에

stock : 4 dates : [4, 10, 15, 20] supplies : [20,40,5,10] k : 50

일 경우를 보자

4일차에 20만큼 받았기 때문에 24일 전까지는 여유가 있다.

이 때, 10일 15일 20일 날 각각 40, 5, 10은 받을 수도 안 받을 수도 있기 때문에 임시로 저장을 해둔다.

24일이 되서 supplies가 0이 되었을 때 10, 15, 20일날 받았어야 했을 구호품 중 최대 값을 찾는다.

 

이것이 가능했던 것은 정확한 일수를 물어 보는 것이 아니라

몇번 지원 받아야 하는가만 따지면 되기 때문이다.

#include <string>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
priority_queue<int, vector<int>,less<int>> temp;
 
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0;
    priority_queue<int, vector<int>, less<int>> suppliesQ;
    int idx=0;
    for(int i =0 ; i<k; i++) {
        if(dates[idx] == i) {
            suppliesQ.push(supplies[idx]);
            idx++;
        }
        if(stock == 0) {
            stock = stock + suppliesQ.top();
            suppliesQ.pop();
            answer++;
         }
        stock--;
    }
 
 return answer;
}

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
 
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int,vector<int>,less<int>> maxQ;
    priority_queue<int,vector<int>,greater<int>> minQ;
    for(string cmdAll : operations) {
        char cmd = cmdAll[0];
        int value = stoi(cmdAll.assign(cmdAll.begin()+1,cmdAll.end()));
        if(cmd == 'I') {
            maxQ.push(value);
            minQ.push(value);
        }else{
            if(value == 1) {
                if(maxQ.empty()) continue;
                if(maxQ.top() == minQ.top()) minQ.pop();
                maxQ.pop();
            }else{
                if(minQ.empty()) continue;
                if(minQ.top() == maxQ.top()) maxQ.pop();
                minQ.pop();
            }
        }
        if(maxQ.top() < minQ.top()) {
            while(!minQ.empty()) minQ.pop();
            while(!maxQ.empty()) maxQ.pop();
        }
    }
    
    if(maxQ.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }else{
        answer.push_back(maxQ.top());
        answer.push_back(minQ.top());
    }
    return answer;
}