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

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

힙 문제는 우선순위 큐를 사용하는게 좋다해서 우선순위 큐를 찾아보고 풀었습니다.

 

priority_queue<int, vector<int>, greater<int>> pq;

타입, 포함된 타입, 정렬방법 이렇게 생성할 수 있습니다.

 

문제에서 최소 몇번을 해야하냐고 물었기 때문에, 정렬을 하여 작은 값들 부터 계산해 나갑니다.

우선순위큐의 top()는 마지막 원소를 확인합니다. 따라서 내림차순인 greater를 사용합니다.

작은 값들부터 계산하고 스코빌 지수를 다시 큐에 마지막에 넣으면서, 마지막 원소가 K를 넘는지 확인합니다.

 

pq의 크기가 1이면 pq의 남은 하나의 원소는 K보다 작고 더 이상 계산할 수 없으므로 -1을 리턴합니다.

 

#include <string>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int solution(vector<int> scoville, int K) {
	int answer = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	vector<int>::iterator it;
	for (it = scoville.begin(); it != scoville.end(); ++it) {
		pq.push(*it);
	}
	while (pq.top() < K) {
		if (pq.size() == 1)
			return -1;
		int a = pq.top(); pq.pop();
		int b = pq.top(); pq.pop();
		pq.push(a + (b * 2));
		++answer;
	}
	return answer;
}