[Programmers]#Level2_더 맵게, 우선순위 큐, 최소 힙

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 우선순위 큐

 

[자료구조]#7_우선순위 큐

우선순위 큐는 원소들이 우선순위에 따라 정렬된 연결 자료구조입니다. 우선순위 큐는 삽입 순서와 무관하게, 우선순위가 가장 높은 원소가 먼저 제거되는 특징을 갖고 있습니다. 일반적으로, 힙 자료구조를 통해 우선순위 큐를 구현합니다. 힙 자료구조를 통해 우선순위 큐는 삽입/제거 수행 시 내부적으로 정렬 작업을 수행하여, 항상 정렬된 상태를 유지합니다.

 

2. 우선순위 큐에서 스코빌 지수 낮은거 2개 뽑아서 합쳐

 

1. 최소 힙을 구성하는 우선순위 큐를 선언하고, 주어진 스코빌 지수를 모두 삽입해줍니다.
2. 우선순위 큐를 순회하며, 우선순위가 가장 높은(스코빌 지수가 가장 낮은) 값을 기준 스코빌 지수와 비교합니다. 이때, 스코빌 지수가 가장 낮은 음식이 기준 스코빌 지수보다 낮다면, 2개 원소를 pop()하고, 하나의 값으로 만들어 다시 우선순위 큐에 삽입해줍니다.
3. 가장 낮은 스코빌 지수가 기준 스코빌 지수보다 높을 때까지 위 동작을 반복해줍니다. 그리고, 섞은 횟수를 세어 결과를 반환해주면됩니다.

 

---

 

#3. 코드

 

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

    while (!pq.empty() && pq.size() > 1 && pq.top() < K)
    {
        int A = pq.top();
        pq.pop();

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

        pq.push(A + (2 * B));
        answer++;
    }

    return answer;
}

 

---