[L2] 프로그래머스 더 맵게 C++ 우선순위 큐

리뷰

프로그래머스

 

모든 음식의 스코빌 지수를 K 이상으로 만드는 문제

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. 오름차순으로 정수를 정렬하는 우선순위 큐 pq를 초기화 한다.
2. scoville 벡터에 존재하는 값들을 모두 pq에 추가해 준다.
3. pq의 사이즈가 2이상이고, pq의 top이 K보다 작다면 계속하여 반복문을 실행해 준다.
4. pq에서 두개의 음식 foo1, foo2를 꺼내주고 new_food를 food1 + food2 * 2로 초기화 해준다.
5. answer을 1만큼 증가시키고 new_food를 pq에 추가해 준다.
6. 모든 반복문을 마친 후 pq가 비지 않았고, pq의 top이 K보다 작다면 answer을 -1로 초기화 해준다.
7. answer에 저장된 값을 리턴해 준다.

 

참고 사항

scoville의 원소는 각각 0 이상 1,000,000 이하고, K는 0 이상 1,000,000,000 이하이다, int범위 내에서 처리할 수 있다.

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return해야 한다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

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