[프로그래머스] Lv.2 더 맵게 c++

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

프로그래머스

 

Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 이를 위해 아래와 같은 규칙으로 두 음식을 섞습니다:

• 새로운 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 × 2)

모든 음식의 스코빌 지수가 K 이상이 될 때까지 섞어야 하며, 최소 몇 번 섞어야 하는지를 구해야 합니다.

풀이 방법

우선순위 큐를 사용하면 쉽게 풀 수 있습니다.

우선순위 큐의 값은 내림차순으로 정렬되기에 입력받는 값에  -를 붙여 오름차순으로 정렬해 줍니다.

이후 스코빌 지수가 가장 낮은 두 값을 queue에서 꺼내 섞고 다시 push 해주면 됩니다.

 

모든 음식의 스코빌 지수가 목표치 K 이상이 되면 반복을 종료하고, 섞은 횟수를 반환합니다.

만약 큐에 값이 하나만 남았는데도 목표치를 달성하지 못했다면, 더 이상 작업이 불가능하므로 -1을 반환합니다.

풀이 코드

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

using namespace std;

priority_queue<int> pq;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    for(int i=0; i<scoville.size(); i++) pq.push(-scoville[i]);
    
    while(!pq.empty()){
        int food1 = pq.top();
        pq.pop();
        if(pq.size()>=1 && -food1 < K){
            int food2 = pq.top();
            pq.pop();
            pq.push(food1 + food2*2);
            answer++;
        }
        else if(-food1 >= K) return answer;
    }
    return -1;
}