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

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

코딩테스트 연습 - 더 맵게

---

 문제 풀이

우선순위 큐를 사용하면 아주 쉽게 풀 수 있는 문제이다.

큐를 우선 오름차순으로 정렬해준다. 

맨 앞에 오는 값들은 스코빌 지수가 작은 순서대로 위치할 것이고

맨 앞의 스코빌 지수가 기준인 K보다 크다면 그 이후의 모든 값들은 K보다 크다.

따라서, 맨 앞의 두 개를 계산해주고 K보다 큰지만 따져주면 된다.

큐의 크기가 1인데 K보다 낮다면 실패한 것이므로 -1을 리턴해주면 된다.

 느낀 점

처음에는 벡터를 사용하고 계속 정렬을 해서 코드를 구현했다. 하지만 효율성에서 너무 떨어져서 우선순위 큐를 통해서 구현했더니 아주 성공적이었다. STL 컨테이너에 대해서 많이 공부했다고 생각했는데 우선순위 큐를 바로 떠올리지 못한 점에서 아직은 많이 부족한 것 같다.

 코드

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