[프로그래머스]힙(Heap) : 라면공장 (level 2)(c++)

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

프로그래머스

 

 

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

using namespace std;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {

    // 최대 힙 선언(우선순위 큐)
    priority_queue<int, vector<int>, less<int>> pq;
    
    int cnt = 0;
    int strt = 0;

    // stock : 버틸 수 있는 날짜. stock의 숫자에 해당하는 날까지 버틸 수 있다.
    // 즉, stock은 결국 k 만큼 있어야 한다.
    while (stock < k)
    {
        /*
            큐 : "버틸 수 있는 날짜까지" 선택 가능한 공급들.
            ex) 4일에는 10일에 들어오는 공급을 선택할 수 없다.

            push한 이후에는 중복해서 큐에 넣지 않도록, strt 인덱스를 증가시켜 준다.
        */
        for (int i = strt; i < dates.size() && dates[i] <= stock; ++i)
        {
            pq.push(supplies[i]);
            ++strt;
        }
            
        // 최소 공급 횟수를 위해 최대 공급양부터 선택한다.
        stock += pq.top();
        pq.pop();
        ++cnt;
    }

    return cnt;
}

 

처음에는 대체 이문제에 힙이 왜 필요한가 한참 고민했다.

 

이 문제를 dp나 다른 방법이 아닌, 힙(우선순위 큐)으로 풀어야 하는 이유는 다음과 같다.

• 일단 시간/메모리 제약 ㅋㅋ
• 선택 횟수만 알면 된다. 어느 시점에 어떤 선택을 하냐는 건 결과적으로 중요하지 않다.
• 그리고 최소 선택 횟수가 필요하니 최대 힙이 필요하다.

 

 

그러면 어떻게 해서 왜 "시점의 선택"이 필요없는지 살펴보자.

아래와 같은 예시로 설명하겠다.

stock	dates	supplies	k	result
4	[4,10,15]	[20,5,10]	30	2

 

 

먼저 stock의 값은 버틸 수 있는 날짜를 뜻한다.

stock값이 4라면, 4일까지는 버틸 수 있다는 뜻이다.

 

그렇다면 결국 (stock + 공급 총합) >= K 가 되어야 한다는 결론이 나온다.

 

 

4일까지 존버하면, 선택할 수 있는 공급이 하나 생긴다

 

큐는 "선택 가능한 공급들의 목록" 이다.

D일이 되기 전에는 D일에 들어오는 공급을 선택할 수 없다.

즉, date[i] <= stock 이 되어야 선택 가능하다.

stock이 4일때는 4일 이전에 들어오는 공급을 우선순위 큐에 push한다.

 

 

짠! 이제 우리는 4 + 20 = 24일까지 버틸 수 있다. 하지만 아직 모자라...

 

최대 힙 우선순위 큐는 가장 큰 값이 top에 있다.

stock에 큐.top()을 더하면, 큐의 최대값이 더해지게 된다.

이제 20이 충전되어 stock이 24가 되었다. 

 

그러면 24일까지 버티면서 선택 가능한 공급 2개를 우선순위 큐에 push하자.

 

 

짠! 이제 stock이 39가 되어 K=30을 훌쩍 넘었다. 끝 

 

그러면 stock에 큐.top()을 더하면, 두 공급값 중 더 큰 값인 10이 더해질 것이다.

즉, 15일에 들어오는 공급이 선택되게 된다.

 

이제 stock의 값(39)이 K(30)를 넘었으므로 

더이상 공급을 선택할 필요 없이 종료한다.

 

만일 K = 40이었다면,

while문의 다음 턴에 10일의 공급 5가 더해져

stock = 44가 되고 while문의 종료조건을 만족하게 된다.

(이때, 더이상의 선택 가능한 공급은 없으므로 새로 큐에 들어오는 공급은 없다.)

 

 

이 과정에서 따로 분기문으로 선택을 제어할 필요가 없다.

큐에 "선택가능한 공급"을 push하기만 하면 되고

그러면 stock이 k를 넘을때까지 자동으로 최대값이 더해져,

최소의 횟수로 공급을 선택할 수 있다.

 

설명 끝

 

 

 

우선순위 큐 STL의 기본 사용법을 참고한 페이지:

https://twpower.github.io/93-how-to-use-priority_queue-in-cpp

[C++] C++ STL priority_queue 기본 사용법과 예제