프로그래머스(힙; 더 맵게) c++

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

using namespace std;

int solution(vector<int> scoville, int K) 
{
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    int count = 0;
    
    while(pq.top() < K)
    {
        if (pq.size() < 2) return -1;
        
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        
        pq.push(first + second * 2);
        ++count;
    }
    
    
    return count;
}

 

해설:

먼저, k는 스코빌의 기준으로 해당 기준에서 모자란 원소가 하나라도 존재할경우

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

위 수식을 적용한다(k=5라는 기준에서 가장 맵지 않은 지수 = 1, 두번째로 맵지 않는 지수 = 5여도 -> 1+5*2로 하여금 적용한다).

하지만, 해당 수식을 적용하고 해당 배열에 삭제, 삽입이 번거롭고 정렬을 vector로만 하기에는 까다롭기에 priority_queue를 이용하여 해결한다(#include <queue>).

 

priority_queue<int, vector<int>, greater<int>> (int형, vector 컨테이너, 비교방식(less->최댓값, greater->최솟값)

첫번째: priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end()); 를 이용하여 스코빌 자체를 넣어 적용(int형의 vector컨테이너, greater 비교방식을 사용; less를 사용할경우에는 priority_queue<int> 으로 선언해도 됨) count 선언.

두번째: while문에서 pq.top()->최상단 노드의 값 을 조건으로 걸어 K보다 작을 경우 계속 실행함(최솟값을 위로 올리기때문에 K보다 작으면 하나이상이 K보다 작다는 가능성을 표출).

세번쨰: 배열이 2보다 작을경우에 수식을 적용 못하기에 -1을 반환 그리고 first와 second를 순차적으로 top() 호출하여 대입하고 pop()을 이용하여 파괴하여 배열을 정리한다(first먼저하고 second를 해야 배열의 앞부분이 사라져 second->first로 바뀌기 때문).

네번째: 수식을 적용하여 pq.push()를 하고 count를 증가(비교 방식을 이용하여 정렬하기에 그냥 push()만 해줘도 된다).