라면공장 (프로그래머스)

 

공급 받는 횟수가 최소가 되는 방법은 수량이 많은 순으로 공급 받으면 된다.

 

공급 받을 날짜가 되면 그 날짜의 밀가루 수량을 힙에 추가한다. (여기서 힙은 최대힙) 

그리고 밀가루가 다 떨어 졌을때 힙에서 최대 수량의 밀가루를 꺼내어 공급받은 후 그 횟수를 올려주면 된다.  

이 과정을 0번째 날 부터 k-1번째 날까지 반복한다면 밀가루 수량을 k날까지 맞출 수 있게된다.

 

C++에서는 힙의 원리가 적용된 'STL priority_queue'를 제공하므로 이것을 사용하면 간편하게 문제해결을 할 수 있다.

 

코드는 다음과 같다.

#include <vector>
#include <queue>
using namespace std;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0;
    // 힙 선언. 최대 힙으로 설정을 바꾼다.
    priority_queue<int, vector<int>, less<int>> q; 
    int index = 0;
    // k-1번째 날까지 반복한다. (k번째 날에는 다시 밀가루를 공급받으므로)
    for(int i = 0; i < k; ++i)
    {
        // 공급 받을 날짜가 되었으므로 
        // 힙에 그 날짜의 공급 가능한 밀가루 수량을 집어넣는다.
        if(dates[index] == i)
        {
            q.push(supplies[index]);
            ++index;
        }
        
        // 밀가루가 비었다면 공급받는다.
        if(stock == 0) 
        {
            // 가장 수량이 많은 순으로
            stock += q.top();
            q.pop();
            ++answer;
        }
        --stock;
    }
    return answer;
}