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

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

프로그래머스

Lv. 2

---

 

priority queue(우선순위 큐)를 사용해 풀이하는 문제.

우선순위 큐를 사용하면 최솟값이나 최댓값을 빠르게 찾아낼 수 있다. 왜냐하면 값을 새로 삽입할 때마다 우선순위에 따라 자동으로 정렬이 되기 때문이다.

우선순위 큐를 구현하기 위해서는 C++의 표준 라이브러리(STL)에 포함된 std::priority_queue 클래스를 사용할 수 있다.

이 클래스는 힙(Heap)을 사용하여 구현되어 있으며 기본적으로 우선순위가 높은 요소가 우선 처리(내림차순)되는 자료구조이다.

 

💡 풀이

1. 오름차순으로 정렬되는 priority queue를 선언한다.

이렇게 하면 priority queue에 데이터를 삽입할 때마다 큐의 원소들이 오름차순으로 자동으로 정렬된다.

즉, priority queue의 top(맨 앞)에는 자동으로 가장 작은 원소가 온다.

2. 큐에 scoville의 원소를 모두 집어넣은 다음, while문을 돌 때마다 큐의 원소를 2번 pop하고, 새로운 원소를 1번 push하는 작업을 반복한다.

3. top이 K 이상이 되면 answer를 리턴한다.

 

주의)

처음부터 큐의 top이 K 이상인 경우를 고려해야 한다. (이 경우를 고려하지 않으니 테스트 케이스 18번에서만 유일하게 에러가 발생했다.

 

 

#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 (int n : scoville)
        pq.push(n);
	
    // 처음부터 최소 원소가 K 이상일 때
    if (pq.top() >= K)
        return 0;

    while (pq.size() > 1) {
        int mix = 0;

        mix += pq.top();
        pq.pop();
        mix += pq.top() * 2;
        pq.pop();

        pq.push(mix);
        answer++;

        if (pq.top() >= K)
            return answer;
    }

    return -1;
}