프로그래머스 더 맵게

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

코딩테스트 연습 - 더 맵게 | 프로그래머스

해당 문제는 Heap 문제였다.

문제에서 주어진 조건 그대로 heap을 구성해서 우선순위가 높은 음식을 2개를 뽑아와서 섞은 뒤 다시 넣는 방식을 통해 정답을 찾을 수 있었다.

다만 주의해야할 점은 C++ priority Queue의 우선순위 비교함수는 greater가 0보다 1이 더 크다는 기준으로 생각해야 한다(매번 헷갈리는 중...).

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0, found =0;
    priority_queue<int, vector<int>, greater<int>> heap;
    
    // heap에 삽입
    for(int i=0;i<scoville.size();i++)
        heap.push(scoville[i]);
    
    // 통과할 때 까지 섞은 횟수
    while(heap.size()>=2 && !found){
        // 1st, 2nd 가져오기
        int first = heap.top();
        heap.pop();
        int second = heap.top();
        heap.pop();
        
        // 섞기
        int item = first + (second*2);
        heap.push(item);
        answer++; // 섞기 1회 증가
        
        // 통과 확인
        if(heap.top()>=K)
            found=1;
    }
    
    // 정답 없음
    if(found ==0)
        return -1;
    
    // 정답 반환
    return answer;
}