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

문제 링크

코딩테스트 연습 - 더 맵게

 

 

 

풀이

우선순위 큐를 이용하여 푸는 문제다

 

// init

우선순위 큐(priority_queue)를 작은 것이 먼저 나오도록 order를 바꿔준다.

pq의 생성자{pq(scoville.begin(), scoville.end())}로도 해도 되지만 for문을 이용해서 push해주었다.

 

// process

우선순위 큐의 top()은 가장 작은 원소값(가장 안매운 스코빌 지수)이 나온다.

이를 이용해서 pop()을 두 번한다.

cur = 가장 작은 원소값, next = 두 번째로 작은 원소값을 문제에 나온 식에 대입(mix = cur + next * 2),

이를 예제에 나온 것처럼 다시 우선순위 큐에 push해준다.

 

그렇게 반복문을 탈출하는 문은 다음과 같다.

1. 가장 작은 원소가 K이상일 때(모든 원소가 K 이상이 된다)

2. 우선순위 큐가 비었을 때(첫 번째 pop() 할 때 적용)

 

 

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

using namespace std;

// 섞은 음식 스코빌 지수 = 가장 안매운 스코빌 지수 + (두번째로 안매운 스코빌 지수 * 2)
// 모든 음식의 스코빌 지수 K 이상 될 때까지 반복

// 음식 스코빌 지수들 scoville
// K 이상

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // init
    priority_queue<int, vector<int>, greater<int>> pq;      // 작은 것이 먼저 나오도록
    for(int e: scoville) pq.push(e);
    
    while(true){
        int cur = pq.top();     // 가장 안매운 스코빌 지수
        pq.pop();
        if(cur >= K) break;
        if(pq.empty()) {answer = -1; break;}
        int next = pq.top();        // 두 번째로 안매운 스코빌 지수
        pq.pop();
        int mix = cur + next*2;     // 섞기
        pq.push(mix);
        answer++;       // 횟수 증가
    }
    
    return answer;          // 모든 음식 스코빌 지수를 K 이상으로 만들기 위한 최소 횟수 리턴 or -1
}