프로그래머스 더 맵게

N이 매우 크면서 매번 정렬을 해야하므로 힙 구조를 쓰는 것이 올바르다. 기본적으로 내림차순 정렬인 우선순위 큐를 functional 함수에 있는 greater<int> cmp 함수를 써서 내림차순으로 정렬할 수 있다. 그래서 맨 뒤에서 우선순위가 높기 때문에 작은 수가 먼저 pop하게 되어진다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_더맵게.cpp

 

	#include <queue>
	#include <iostream>
	#include <functional>
	using namespace std;
	int solution(vector<int> scoville, int K) {
	int answer = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < scoville.size(); i++) {
	pq.push(scoville[i]);
	}
	while (1) {
	if (pq.size() <= 1) {
	return -1;
	}
	if (pq.top() >= K) {
	break;
	}
	int a = pq.top();
	pq.pop();
	int b = pq.top();
	pq.pop();
	int c = a + b * 2;
	pq.push(c);
	answer += 1;
	}
	return answer;
	}

view raw Programmers_더맵게.cpp hosted with ❤ by GitHub