[프로그래머스 문제풀이] 12. 더 맵게

우선순위 큐에 스코빌 지수를 전부 넣는다.
greater를 사용해 작은 숫자가 앞에 오도록 정렬한다.

priority_queue<int, vector<int>, greater<int>> scov_queue(scoville.begin(), scoville.end());

큐의 원소가 1개만 있는 지 검사하는 코드를 반복문에서 앞쪽에 놓으면 테스트케이스에 걸린다.
답이 결정되었는 지 확인한 후에 큐의 사이즈를 검사해야 한다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

#include <iostream>

using namespace std;

int solution(vector<int> scoville, int K) {
	priority_queue<int, vector<int>, greater<int>> scov_queue(scoville.begin(), scoville.end());

	for (size_t cnt = 0; ; cnt++)
	{
		int first_min = scov_queue.top();
		if (first_min >= K)
			return cnt;

		if (scov_queue.size() == 1)
			return -1;

		scov_queue.pop();

		scov_queue.push(first_min + scov_queue.top() * 2);
		scov_queue.pop();
	}
}

int main()
{
	cout << solution({ 1, 2, 3, 9, 10, 12 }, 7) << endl;
}

실행결과

2

더 맵게 문제 링크