[C++] 우선 순위 큐(Priority Queue) / 힙(Heap) : 프로그래머스 스코빌 지수(Scoville) 문제 풀이

 

오늘의 주제는 '우선순위 큐'이다. 이는 내부적으로 '힙(Heap)' 자료구조를 구현하고 있기 때문에 함께 익혀보도록 하자. 또한 우선순위 큐를 활용한 프로그래밍 문제를 풀어보며 응용하는 시간도 가져보자.

 

Priority Queue란? 

C++의 컨테이너 어댑터인 priority queue는 큐의 원소 중 가장 큰 값을 우선 순위로 두고 오름 차순으로 원소들을 배열하는  큐의 한 종류이다. 어떤 원소의 삽입(push)나 삭제(pop)가 발생할 경우 큐의 우선순위에 맞추어 정렬한다. 자료구조 Heap으로 구현되었기에 push에 의한 정렬은 O(logN)의 시간 복잡도를 가진다. 사용법과 기본 매서드는 아래와 같다.

 

1.  priority_queue 선언

• 헤더 파일<queue>를 include 해준다: #include <queue> pq;
• 디폴트(오름차순) 우선 순위 큐 선언: priority_queue <int> pq;
• 응용 버전 내림차순 우선순위 큐 선언:  priority_queue <int, vector <int>, greater <int>> pq;

+ 참고로 우리가 스코빌 문제 풀이에서 사용할 우선순위 큐 선언은 '내림차순' 우선 순위 큐 선언이다.

 

 2. priority_queue 활용

• int top(): 맨 앞에 있는 원소 반환한다.
• void push(int n): n을 큐에 삽입하는 동시에 큐를 우선순위에 맞게 정렬한다.
• void pop(): 맨 앞에 있는 원소(=pq.top())를 삭제하는 동시에 큐를 우선 순위에 맞게 정렬한다.
• int size(): 큐의 크기를 반환한다.

더욱 자세한 priority_queue에 대한 설명은 아래 컨퍼런스 링크를 참조하자

std::priority_queue - cppreference.com

 

프로그래머스 힙(Heap) 
연습 문제_더 맵게(스코빌 지수): 난이도 中

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

< 문제 풀이 >

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    //작은 수부터 정렬되는 우선순위 큐 선언, scoville 벡터 삽입
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(),scoville.end());

    //pq에서 제일 작은 값이 K보다 작고, pq에 2개 이상의 음식이 남아있을 동안만 실행
    while (pq.top()<K && pq.size()>1) {
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        pq.push(first + 2 * second);
        answer++;
    }
    if (pq.top() < K) return -1; //pq에 남아있는 값이 K보다 작다는 건 어떻게 해도 K를 못 넘긴다는 뜻
    return answer;
}

작은 수부터 정렬되도록 우선순위 큐를 선언하고, scoville vector를 삽입해준다. 이후 while문을 사용해서 스코빌 지수가 가장 낮은 음식과 두 번째로 낮은 음식을 섞어서 큐에 삽입하며 스코빌 큐를 계속해 갱신해 나가는 작업을 구현해준다. 이후, 큐에 남은 음식이 여전히 K보다 낮다면, 이는 while문에서 pq에 음식이 하나밖에 남지 않아 빠져나왔다는 뜻이고, 그 하나마저 K를 넘을 수 없으므로 -1을 반환해준다. 큐를 사용해서 문제를 재밌게 풀 수 있었다. 

 

코딩테스트 연습 - 더 맵게