[프로그래머스] 더 맵게 (C++)

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

프로그래머스

Heap 힙 (우선순위 큐)

n개의 음식의 스코빌지수가 배열로 주어지고, 이 음식들의 최소 스코빌 지수가 K이상이 되도록 음식을 섞을 수 있다고 할 때, 최소 몇번 섞어야 하는지 반환하는 문제. (모든 음식을 섞어도 스코빌지수가 K를 넘지 않는다면 -1을 반환)

음식을 섞는 다는 것은, 섞인 음식의 스코빌 지수 = 최저스코빌지수 음식의 스코빌 지수 + 두번째로 스코빌지수가 최저인 음식의 스코빌 지수*2 이다. 

 

접근방법 

갱신되는 음식들의 스코빌지수를 담고 있으면서, 늘 정렬되어있는 자료구조가 필요하다. = 우선순위 큐 (오름차순)

그러면 top 두개를 빼서 그 둘을 섞은 후에 섞인 음식의 스코빌 지수를 다시 우선순위큐에 넣으면 된다.

이 과정을 음식들의 최저 스코빌 지수가 K 이상이 될 때까지 혹은 모든 음식을 섞어버려서 음식이 1개만 남았을 경우 까지 반복한다.

음식이 1개만 남았을 경우, 그 한개의 스코빌지수가 K 이상인지 아닌지는 반복문을 나와서 확인한 후에,

이상이면 반복횟수를 리턴하고, 미만이면 -1을 반환하면 된다.

그리고 음식이 2개이상 남았을 경우, 음식을 다 섞지 않아도 모든 음식의 스코빌지수가 K이상이 되었다는 의미이므로 반복횟수를 반환한다.

이때 반복횟수(answer)은 반복문에서 음식을 섞어서 다시 우선순위큐에 넣을 때마다 1씩 증가시킨다.

 

오답노트

priority_queue 오름차순 = <int, vector<int>, greater<int>>

priority_queue 내림차순 = <int, vector<int>, less<int>>

커스텀 -> cmp (struct cmp -> operator() 오버라이드)

 

그리고 반복문에서 pq에서 두개를 빼서쓰는데 이러러면 pq에 두개이상의 원소가 있다는걸 보장해줘야 하기 때문에

반복문 조건에 pq에 2개 이상의 원소가 있을 경우만 들어가도록 조건 추가해줘야함

 

소스코드

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

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(pq.top() < K && pq.size() >= 2){
        int least = pq.top();
        pq.pop();
        int sec_least = pq.top();
        pq.pop();
        
        int mixed = least + sec_least*2;
        pq.push(mixed);
        answer++;
    }
    
    if(pq.top() < K){
        return -1;
    }
    
    return answer;
}