프로그래머스 더 맵게

문제

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

코드

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
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.top()<K)
    {
        if (pq.size() == 1 && pq.top() < K)
            return -1;

        int temp = pq.top();
        pq.pop();
        temp+=pq.top() * 2;
        pq.pop();
        pq.push(temp);
        answer++;

    } 

    return answer;
}

풀이

문제에서 주어진 배열의 값들중 k이하의 값들을 섞어서 k이상의 값으로 만드는데 최소횟수로 섞는게 뽀인트입니다

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

코드를 보면 우선순위 큐를 만들어서 배열의 값들을 다 넣습니다

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

만약 우선순위 큐의 가장 앞에 있는 값(제일 작은 값)이 k보다 크다면 큐의 다른값들도 모두 k보다 큰것이기 때문에 반복문을 종료합니다

while (pq.top()<K)

만약 큐에 값이 1개밖에 없는데 k보다 작다면 더이상 합칠수 없기 때문에 1을 반환합니다.

if (pq.size() == 1 && pq.top() < K)
     return -1;

나머지는 문제에서 주어진 식을 따라서 구현하고 반복문 한번마다 카운팅을 해주면 됩니다.