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

문제

프로그래머스 힙 - 더 맵게 (Level 2)

코딩테스트 연습 - 더 맵게

 

---

문제 풀이

접근 방식

아래와 같은 방법으로 새로운 음식을 만들 때,

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하는 문제이다.

 

섞은 음식의 스코빌 지수를 구하는 계산식

 

가장 작은 값과 두 번째로 작은 값을 지속적으로 구해야하는 문제이기 때문에,

우선순위 큐를 사용하여 min heap을 구현해주었다.

 

우선순위 큐에 모든 음식의 스코빌 지수를 넣어준 후,

우선순위 큐의 top에 있는 값(최솟값)이 K 이상일 때까지 위의 계산식을 사용하여 음식을 섞어주었다.

 

우선순위 큐의 사이즈가 1일 때는 더 이상 음식을 섞을 수 없는 상황이므로 -1을 리턴해주도록 구현하였다.

 

---

풀이 코드 - C++

#include <string>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int> > pq;
    for(int i: scoville)
        pq.push(i);
        
    while(true) {
        if(pq.top() >= K)
            return answer;
        if(pq.size() == 1)
            return -1;
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a+b*2);
        answer++;
    }
}

실행 결과

실행 결과 : 통과 (100.0)