[C++] 프로그래머스 - 더 맵게 (힙)

이번 포스팅은 프로그래머스의 힙 문제 중 하나인 더 맵게를 풀어봤습니다. 풀기에 앞서 힙에 대해 간단히 설명하자면 다음과 같습니다.

---

1. 스택: LIFO (Last in, first out) 구조
2. 큐: FIFO (First in, first out) 구조
3. 힙: 우선순위 큐 (Priority Queue) 구조

---

스택과 큐는 쉽게 구분이 갑니다. 스택은 바구니가 있으면, 물건을 바구니 안에 차곡차곡 쌓아올린다고 생각하면 됩니다. 물건을 꺼낼때는, 가장 최근에 넣은 물건이 꺼내집니다. 반면 큐는, 같은 바구니긴한데 물건을 꺼낼 때 밑에서 꺼낸다고 이해할 수 있습니다. 즉, 넣은지 가장 오래된, 가장 먼저 넣은 물건을 먼저 빼내는 식인 셈입니다. 큐는 어떤 일처리를 하는데 있어서 순서대로 진행해야할 때 많이 사용하곤 합니다.

---

그렇다면 우선순위 큐는 대체 뭘까요. 말그대로 큐의 형태이긴 하나, 우선순위를 갖는다는 말입니다. 운영체제에서 작업 스케쥴링을 할 때 사용되곤 하는데, 힙은 우선순위 큐를 구현하는 방법 중에 하나입니다. Max Heap, Min Heap의 이진트리 형태로 표현될 수 있으며, 상세 내용은 여기를 참조하시면 됩니다.

---

우선순위 큐 Max Heap, Min Heap 정의

Max와 Min heap은 선언하는 부분이 약간 다릅니다. 디폴트는 Max heap 입니다.

• Max: priority_queue <int> pq;
• Min: priority_queue <int, vector<int>, greater<int> > pq;

---

문제 정의

---

---

접근 방법

• 2번씩 차례대로 가장 top에 위치한 원소를 가져온 뒤 pop 합니다. (일반 큐는 front와 pop을 사용하는 것과 다름에 주의)
• 스코빌 식에 의해 연산된 결과값을 힙에 추가합니다.
• while loop의 조건식에 주어진 K 조건과 맞는지 비교합니다.
• 만약 남은 힙의 사이즈가 1이고, K 조건에 맞지 않다면, 더 이상 연산을 할 수 없으므로 -1을 반환합니다.

---

전체 코드

---

코드는 간단하여 첨부합니다.

---

#include <string>
#include <vector>
#include <iostream>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // make priority Queue
    priority_queue <int, vector<int>, greater<int> > p;
    for (int i=0; i<scoville.size(); i++) {
        p.push(scoville[i]);
    }
    
    // stop it when p.top is greater than K.
    std::cout << p.top();
    while(p.top() < K) {
        int temp1 = p.top();
        p.pop();
        int temp2 = p.top();
        p.pop();
        p.push(temp1+(temp2*2));
        answer++;
        
        if (p.top() < K && p.size() == 1) {
            answer = -1;
            break;
        }
        
        
        
    }
    
 
    
    return answer;
}

___