[프로그래머스] 2단계 - 더 맵게

문제 설명

모든 음식이 스코빌 지수를 K 이상이 될 때 까지 반복해서 섞을 때, 섞어야 하는 최소 횟수를 return

https://school.programmers.co.kr/learn/courses/30/lessons/42626#

프로그래머스

 

문제 풀이법

스코빌 지수가 항상 정렬이 되어야 했기 때문에 priority_queue를 사용하여 정렬 상태를 유지해 주었다

큐에 들어있는 값이 1개가 될 때 까지 음식을 섞어주면 되는데, 이때 맨 앞의 값이 K보다 크면 다른 음식들의 스코빌 지수도 모두 K보다 크다는 것이 보장이 될테니 while문을 빠져나간다

 

이후 큐의 길이가 1이 아니면 지금까지 섞은 횟수를 return해준다

만일 큐의 길이가 1이고, 큐의 맨 앞 값이 K보다 크면 이때도 지금까지 섞은 횟수를 return 해준다 (16, 22, 23번 테스트 케이스가 실패한다면 이 부분을 체크해보세요) 

그렇지 않다면, 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없으므로 -1을 return 한다

 

 

소스 코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> q;
    
    for (int i = 0; i < scoville.size(); i++)
        q.push(scoville[i]);
    
    while (q.size() > 1) {
        if (q.top() >= K)
            break;
        
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        
        int tmp = a + (b * 2);
        
        q.push(tmp);
        
        answer++;
    }
    
    if (q.size() == 1) {
        if (q.top() >= K)
            return answer;
        else
            return -1;
    }
    
    return answer;
}