[프로그래머스] - 더 맵게(C/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 합니다.

입출력 예

 

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

---

[문제 풀이]

프로그래머스 코딩테스트 연습에 힙(Heap) 카테고리에 있는 문제이다.

문제 풀기위해선 우선순위 큐를 사용하는것이 가장 합리적으로 보였다.

 

우선순위 큐는 힙을 이용하여 구현된다고 한다.

힙이라는것은 항상 완전 이진 트리의 형태를 띄어야 한다.

 

완전 이진 트리라는것은 모든 노드의 오른쪽 자식이 있다면 왼쪽 자식이 무조건 있는 이진 트리이다.

즉, 트리의 왼쪽부터 차곡차곡 쌓는 이진 트리라고 할 수 있다.

 

이진 트리라는것은 부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는 트리의 가장 간단한 형태이다.

아래 이미지를 참고하면 좋겠다.

출처 : https://mblogthumb-phinf.pstatic.net/MjAxNzA2MjZfMTQ3/MDAxNDk4NDg4OTQ3MTY3.BL6mxcL1C1_9--at9QOt67hX9cf8RWOEz6UUtRQFiVkg.SwjOWlSTbIq-XvbKggYEvfFYs7pGzNQUnvfoHuBEXfog.JPEG.jerrypoiu/31_simtwolove.jpg?type=w2

 

완전 이진 트리에는 두가지 종류가 있다.

1. 최대 힙 (Max Heap) :  부모 노드의 키 값이 항상 자식 노드들의 키값 보다 크거나 같다.

2. 최소 힙 (Min Heap)  :  부모 노드의 키 값이 항상 자식 노드들의 키값 보다 작거나 같다.

 

우리가 문제에서 사용 할 방법은 최소힙이다.

priority_queue를 사용하기 위해서는 #include <queue>를 해주면 된다.

priority_queue의 기본 형식은 아래와 같다.

출처 :&nbsp;https://en.cppreference.com/w/cpp/container/priority_queue

우리는 scoville vector값을 prioirty_queue에 넣어 주어야 한다.

방법은 여러가지가 있지만 한번에 넣는 방법이 있다.

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

int                          => queue 원소 타입

vector<int>          => 사용할 컨테이너 (vector<T> / deque<T>) 사용 가능

Compare             => 최대힙(less<int>)/최소힙(greater<int>) 

위와 같이 하면 scoville 벡터에 있는 원소들을 pq에 최소힙으로 가장 작은값부터 확인 할 수 있도록 정렬되어 들어간다.

scoville vector에서 가장 작은 값과 두번째로 작은 값을 매번 확인해서 계산식을 수행해야 하기때문이다.

계산된 값을 다시 priority_queue에 push 할때마다 정렬이 갱신된다.

 

준비가 되었다면 우리가 할 일은 아래의 일을 반복하면 된다..

 

1. 맨앞의 값이 K보다 작고 priority_queue에 원소가 있는지 확인 

1-1. K의 값보다 크다면 종료하고 answer 값 리턴

1-2  priority_queue가 비어있다면 종료

1-3  priority_queue에 원소가 있고, 맨 앞의 값이 K의 값보다 작다면 아래의 과정을 수행

 

2.  priority_queue에서 앞의 두 값을 꺼내서 계산을 수행하여 priorty_queue에 push, answer 값 1 증가

3. 1번의 조건에 걸리지 않을때까지 반복문 수행

 

4. 반복문 수행이 종료되었는데도 마지막에 계산되었던 priority_queue의 맨 앞 값이 K보다 작다면 -1을 리턴

 

위의 과정을 코드로 정리하면 아래와 같다. 

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#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());   
    
    int top = pq.top();
    pq.pop();
    while(top < K && !pq.empty())
    {
        answer++;
        top += (pq.top() * 2);
        pq.pop();
        pq.push(top);
        top = pq.top();
        pq.pop();
    }
    if(top < K)
        answer = -1;
    return answer;
}