프로그래머스Lv2 - 더 맵게

코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer  = 0;
    
    int len = scoville.size()-1;
    
    // vector를 우선순위 큐에 저장
    // 내림차순 정렬을 위해 greater<int> 사용
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    for(int i=0;i<len;i++) {
        answer++;
        int num1 = pq.top();
        pq.pop();
        int num2 = pq.top();
        pq.pop();
        pq.push(num1 + num2*2);
        if(pq.top() >= K) break;
    }
    return pq.top() < K ? -1 : answer;
}

추가 정리

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

using namespace std;

void print(vector<int>& vs)
{
	for (auto v : vs)
		cout << v << ' ';
	cout << endl;
}

int solution(vector<int> scoville, int K) {
    
    make_heap(scoville.begin(),scoville.end());
	print(scoville);
    // 입력: [1, 2, 3, 9, 10, 12]
    // 출력: [12, 10, 3, 9, 2, 1]
    return 0;
}

우선순위 큐를 보통 priority_queue를 많이 사용하지만 혹시 vector를 make_heap을 사용해서 쓸 수도 있을 것이다. 여기서 vector를 vec으로 생성했다고 하자.
우선순위큐를 pop() 했을 때 힙의 종류에 따라 최대 값 혹은 최소 값이(이하 최대 값으로 표현) 나오는데 이때 vec[0]은 최대 값이 맞지만 vec[1]이 그 다음으로 큰 값인 지는 알 수 없다.
위 코드의 주석에서 볼 수 있듯이 정렬이 된 게 아니기 때문이다. 따라서 pop()을 두번해줘야 가장 큰 값과 그 다음으로 큰 값을 불러올 수 있다.

풀이 및 소감

우선순위 큐가 바로 떠오르지 않아서 애를 먹었다 ㅠㅠ 요즘 코테도 보면서 어느정도 감을 찾았다고 생각했는데 갑자기 안 떠오르니 막막했다... 얼른 더 문제를 풀면서 감을 익혀야겠다.