프로그래머스 - 더 맵게 - C++

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

프로그래머스

 

#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]);
    
    int t1,t2;
    while(pq.size()>=2&&pq.top()<K)
    {
        t1=pq.top();
        pq.pop();
        t2=pq.top();
        pq.pop();
        
        pq.push(t1+t2*2);
        answer++;
    }
    if(pq.top()<K)
        return -1;
    return answer;
}

모든 음식의 스코빌 지수가 높게 될 때까지 음식을 섞는다. 

이 때, 스코빌 지수가 가장낮은 두개를 계속 찾아야하기 때문에 자동으로 계속 정렬을 해주는 map이나 우선순위큐가 적당하다. 하지만 이 때, 첫 두개의 원소를 계속 빼야하기 때문에 map은 부적절하다. 따라서 우선순위큐를 이용해 구현한다. 

 

오름차순으로 정렬되는 우선순위큐에 원소를 다 대입한다.
만약 pq.top() 이 K보다 작으면 어쨋든 섞어야한다. 

따라서 그 조건일 때 두개를 빼서 섞기를 진행한다. 

 

while문을 빠져나오면 경우는 두가지다. pq.top()이 K보다 높아져서 중간에 종료됐던지 사이즈가 1이 돼서 종료됐던지
pq.top()이 K보다 크면 answer를 리턴하고 작으면 사이즈가 1이될때까지 스코빌지수 K 를 못넘겼기 때문에 -1을 리턴한다.