[프로그래머스 / C++] 더 맵게 풀이

문제 설명

 

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

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

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

<제한 사항>

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

문제 주소: https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

 

 

문제 풀이

 

최소 힙을 만족하는 우선순위 큐를 이용해 문제를 해결합니다. 

 

우선순위 큐(priority queue)는 최대 힙과 최소 힙 두 종류가 있습니다. 최대 힙(max-heap)은 큐 내의 가장 큰 값을 순서대로 반환하고, 최소 힙(min-heap)은 큐 내의 가장 작은 값을 순서대로 반환합니다. 이 문제에선 스코빌 지수가 가장 작은 것 두 개가 필요하므로 최소 힙을 만족하는 우선순위 큐를 이용하는 것입니다. 

 

1. 최소힙을 만족하는 우선순위 큐(pq)에 스코빌 지수 배열의 값을 저장한다.
2. pq에서 가장 작은 값(x)과 두 번째로 작은 값(y)을 꺼낸다. (이때, pq의 원소가 1개뿐이라면 return -1)
3. 새로 만든 음식의 스코빌 지수(x + y*2)를 pq에 저장하고 answer에 1을 더한다. 
4. pq에서 가장 작은 값이 K 이상이 2, 3을 될 때까지 반복한다. 

 

 

 

소스코드

 

// 더 맵게
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
 
using namespace std;
 
// min-heap(최소 힙)을 만족하는 우선순위 큐 선언
priority_queue< int, vector<int>, greater<int> > pq;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
 
    // 최소 힙에 원소 추가
    for (int i = 0; i < scoville.size(); i++) {
        pq.push(scoville[i]);
    }
 
    while (pq.top() < K) {
        int x = pq.top(); // 가장 안 매운 음식의 스코빌 지수
        pq.pop();
        if (pq.empty()) // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
            return -1;
        int y = pq.top(); // 두 번째로 안 매운 음식의 스코빌 지수
        pq.pop();
 
        pq.push(x + y * 2); // 새로 만든 음식의 스코빌 지수 push
        answer++;
    }
 
    return answer;
}

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)