[고득점Kit][힙] 더 맵게 ⭐⭐

[힙] 더 맵게

난이도 ⭐⭐

문제

내 풀이 ⭕

#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(auto & elem : scoville)
    {
        pq.push(elem);
    }
    
    while(true)
    {
        if (pq.size() > 1)
        {
            int sum = pq.top();
            pq.pop();
            sum = sum + 2 * pq.top();
            pq.pop();
            pq.push(sum);
            answer++;
        }
        else
        {
            if(pq.top() < K)
            {
                answer = -1;
            }
            break;
        }
        if(pq.top() >= K)
            break;
    }
    
    return answer;
}

링크 👈 이 포스트에 priority_queue에 대한 정리를 해 두었다.

• top이 언제나 최소값으로 설정되는, 즉 Min Heap을 기준으로 하는 우선순위 큐를 선언해준다.
  • 큐에서 pop() 꺼내기만 해도 최소값이 꺼내진다는게 보장된다.
• 큐 사이즈가 2 이상일 때
  • 큐에서 2개 꺼내는 것 만으로도 최소, 두번째로 최소가 꺼내진다는게 보장 됨
• 큐 사이즈가 1일 때
  • 원소 하나만 남았을 때 K 미만이면 K 이상의 스코빌 지수를 만들 수 없는 것이므로 -1을 리턴

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기