[프로그래머스 LV2] - 더 맵게(minheap) c++

문제

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

프로그래머스

접근방법

기존 vector를 이용해 minheap을 만드는 방법을 배웠다. 

 

기존 vector의 size()가 1인 경우를 고려하지 못해서

계속 실패했다.

 

코드

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    // 스코빌 지수를 오름차순으로 정렬하는 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());

    while (pq.size() > 1) {
        // 가장 작은 스코빌 지수가 K 이상이면 종료
        if (pq.top() >= K) {
            return answer;
        }
        // 현재 스코빌 지수가 가장 작은 음식의 지수
        int first = pq.top();
        pq.pop();
        
        // 현재 스코빌 지수가 두 번째로 작은 음식의 지수
        int second = pq.top();
        pq.pop();
        
        // 새로운 음식의 스코빌 지수 계산
        int newScoville = first + (second * 2);
        pq.push(newScoville); // 새로운 음식을 우선순위 큐에 추가
        
        answer++; // 섞은 횟수 증가
    }
    if (pq.top() >= K) return answer;
    
    // 모든 음식의 스코빌 지수가 K 이상이 되지 않는 경우 -1 반환
    return -1;
}

개선할 점

minheap 만드는 방법을 기억하자.

 

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