[프로그래머스/Level 2] 더 맵게 (C++)

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

스코빌 지수가 낮은 순서대로 2개씩 리턴을 해야하는데, priority_queue를 이용한 최소 힙을 통해 쉽게 구현할 수 있다.

1. 최소 힙 우선순위 큐에 scoville 벡터의 요소들을 넣어주어 자동으로 오름차순 정렬한다.

2. 우선순위 큐의 맨 앞이 가리키는 값이 K보다 작으면서 동시에 우선순위 큐의 사이즈가 1이 아닐때까지 반복문을 진행한다. (우선순위 큐 안에 있는 모든 스코빌 내용들을 섞으면 하나의 원소만 남기 때문에)

3. 우선순위 큐의 원소를 2번 꺼내고, 이를 섞는 과정을 진행한 후 answer 증가

4. 남은 원소의 맨 앞의 값이 K보다 작다면 -1을 리턴, 아니라면 섞은 횟수인 answer를 리턴

 

 

#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(int i = 0; i< scoville.size(); i++) {
        pq.push(scoville[i]);
    }
    
    while(pq.top() < K && pq.size() != 1) {
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        int blending = first + (second * 2);
        pq.push(blending);
        answer++;
    }
    
    if(pq.top() < K) return -1;
    else return answer;
}