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

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

코딩테스트 연습 - 더 맵게

 

풀이

 

우선순위 큐를 사용하면 간단하게 해결 가능한 문제이다.

1. 우선순위 큐에 스코빌 지수가 낮은것부터 정렬되도록 넣어준다.
2. 우선순위 큐의 원소가 2개 이상이고 우선순위 큐의 top의 값이 K보다 작은 동안 loop를 반복한다.
3. loop 내에서는 가장 작은 것 2개씩 pop하고 섞은 스코빌 지수를 계산하여 push한다.
4. loop가 종료된 후 top의 값을 확인하고 이것이 K보다 작으면 answer = -1을 한다.

 

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

using namespace std;

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