문제 푼 날짜 : 2021-08-12

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

접근 및 풀이

주어진 조건을 반복해서 구하기 위해서는 스코빌 지수가 오름차순으로 정렬되면 계산하기 편할 것이라 생각했다.

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

주어진 배열의 길이가 최대 1,000,000라고 했기 때문에 계산해줄 때마다 sort를 하는 것보단 자동으로 오름차순 정렬을 해주는 priority_queue를 이용하였다.
가장 맵지 않은 음식의 스코빌 지수가 K 이상이면 나머지 음식의 스코빌 지수도 K 이상인 것이므로 이를 조건으로 반복하여 계산해주었다.
가장 맵지 않은 음식의 스코빌 지수가 K 미만이면서 음식의 갯수가 2개 미만이라면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이므로 -1을 return 해주었다.

코드

#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;
    
    for (int i : scoville) {
        pq.push(i);
    }
    while (pq.top() < K)  {
        if (pq.size() < 2) {
            answer = -1;
            break;
        }
        int first = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();
        pq.push(first + second * 2);
        answer++;
    }
    return answer;
}

결과

피드백

C++에서 제공하는 STL을 사용법을 익숙하도록 연습해야겠다.