프로그래머스 42626 - 더 맵게 (c++)

프로그래머스 42626 - 더 맵게

문제 링크

생각 및 접근

• 스코빌 지수가 제일 낮은 것과 그 다음으로 낮은 것을 찾아야 하므로 처음에는 C++ STL Algorithm의 sort로 해결하려고 했으나, 정렬하고 두 개 뽑아서 하나 넣고, 정렬하고 두 개 뽑아서 하나 넣고 식의 코드는 시간 효율이 너무 떨어질 것 같았다.
• 그래서 새로 생각해낸 방식이 우선순위 큐 활용하기 (우선순위 큐에 대한 내용 링크)
• 우선순위 큐를 최소 힙으로 선언하여, 우선순위 큐에 scoville의 값들을 다 넣고, 부모 노드 두개만 뽑아서 값을 체크하면 된다.
• 답을 반환하는 시점
  • 우선순위 큐의 top이 K보다 크거나 같을 때 (모든 음식의 스코빌 지수를 K 이상으로 만든 경우)
  • 우선순위 큐의 top이 K보다 작고, 그 값이 우선순위 큐에 존재하는 유일한 원소일 때 (모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우)

코드

#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(auto s : scoville)  pq.push(s);

    while(-1){        
        int low1 = pq.top();
        pq.pop();
        if(low1 >= K)       return answer;
        if(pq.size() == 0)  return -1;

        int low2 = pq.top();
        pq.pop();

        pq.push(low1 + low2 * 2);
        answer++;
    }
}

채점 결과