Problem

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한사항

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

Tip

문제가 길어서 정리하겠습니다.

1. 현재 라면공장에는 stock 만큼의 밀가루 재고가 남아있습니다.
2. 매일 공장에서는 밀가루를 1씩 소모합니다.
3. dates는 해외 공장에서 보급을 받을 수 있는 날입니다. supplies는 해당 날에 보급받는 밀가루의 양입니다.
4. K-1일 까지 공장을 가동하는데 하루라도 밀가루의 양이 0이 되면 안됩니다. (다만 0이 된 날에 밀가루를 공급 받을 수 있다면 괜찮습니다)

이때 supplies를 받는 횟수를 최소하는 수를 구하는 문제입니다.

공급을 받아야하는 날 (stock이 0이 된 경우) dates의 모든 날짜에 공급을 받는다고 가정하고 완전탐색하여 문제를 풀 수도 있겠지만, 길이가 20,000인 입력이 들어올 수 있어 비효율 적일 것 같습니다.

HINT : 현재 부터 0이 될 때까지 밀가루를 모두 공급 받는다고 생각하면 어떤 공급일을 선택하는 것이 최선의 선택인가요?

Solving

k = 30;
stock = 10;
dates = {1, 2, 3, 4, 5, ..., 30};
supplies = {1, 2, 3, 4, 5, ..., 30};

이런 입력이 들어왔다면, stock이 0이 되는 10일째 되는날 밀가루를 공급받아야 합니다. 만약 1일에 1만큼의 공급을 받았다고 한다면, 바로 다음날인 11일에 stock이 0이 되어 다시 공급을 받아야 할 것입니다. 반면, 10일에 10만큼의 공급을 받는다면 앞으로 10일은 더 버틸 수 있습니다. 현재 우리가 선택할 수 있는 최선은 한번에 최대한 많은 양을 공급받는 것입니다. 즉, 10일까지 받을 수 있었던 공급의 수 1, 2, 3, …, 10 중 가장 큰 수를 선택하는 것이 최선이 됩니다.

dates는 오름차순 정렬 되어있습니다. stock이 0이 되는 날을 기준으로 받을 수 있는 모든 공급의 양 중 최대값을 선택하면 공급횟수를 최소화 할 수 있습니다. 일반적으로 최대값은 루프를 돌려서 하나씩 비교하여 찾습니다. 이때 시간복잡도는 O(n)이 됩니다. 하지만, 위에서 설명한 dates, supplies의 길이가 20,000을 넘을 수 있기에 O(n)의 시간복잡도는 시간초과가 될 수 있습니다. 이에 최대값, 최소값을 O(logn)의 시간복잡도로 찾을 수 있는 우선순위 큐를 소개하겠습니다.

우선순위 큐 (Priority Queue)

카페에서 음료를 주문하면 번호표를 받습니다. 직원이 먼저 받은 주문대로 음료를 제조하고 순서대로 받을 수 있습니다. 이러한 구조를 선입선출 (FIFO : First In First Out)이라 부릅니다. 큐(Queue)는 FIFO 구조를 가지는 자료구조입니다. 큐는 push, pop 2가지 동작을 합니다. push 동작은 우리가 번호표를 받는 행위와 같습니다. push 동작으로 자료를 큐의 끝에 집어넣습니다. pop 동작으로 큐에 가장 앞쪽에 있는, 가장 먼저 들어온 자료가 반환됩니다. 이는 먼저온 손님부터 차례대로 대접하는 것과 같습니다. 이렇게 큐는 먼저 들어온 작업을 처리하거나 순서를 관리할 때 많이 사용합니다.

그런데 먼저 들어온 순서말고도 우선순위에 따라 처리해야 하는 일들이 있습니다. 예를들어 파르페를 제조하는데 오랜 시간이 걸려 빨리 만들 수 있는 아메리카노를 먼저 만들거나, 가령 게임하고 있는데 내일 시험인 경우는 시험공부가 우선이겠죠? 아닐 수도 있습니다 일반적인 큐에서는 들어온 순서대로 처리하지만, 우선순위 큐는 우선순위에 따라서 처리합니다. pop할 때 높은 우선순위를 가진 자료가 반환됩니다. 우선순위 큐는 힙 (heap) 구조를 이용하여 우선순위에 따라 자료를 반환합니다.

Heap 구조

출처 : GIPHY

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조입니다. 위 그림과 같이 값이 삽입될 때 마다 항상 값이 정렬되어 들어갑니다. 이때 시간복잡도는 삽입, 삭제시에 전체 자료의 반절씩만 비교하면 되므로 O(logn)의 시간복잡도를 갖습니다. 가장 위에 있는 원소(=루트, root)가 아래에 있는 값들보다 작거나 큰것에 대해 각각 최소 힙, 최대 힙 구조라고 부릅니다. 힙에서 자료를 하나씩 가져오면 루트에 있는 원소를 가져오게 됩니다. 루트의 원소는 항상 heap 안에서 최소이거나 최대입니다. 가장 위에 있는 자료를 반환하면 되므로 O(1)만에 최대, 최소값을 찾을 수 있습니다. 설명이 장황해지니 다른 포스팅에서 힙을 자세히 다뤄보도록 하고 여기서는 개념만 잡고 문제를 풀어보겠습니다.

c++에서는 queue 라이브러리를 include하면 우선순위 큐를 사용할 수 있습니다. 다음 코드는 최대 힙을 사용한 우선순위 큐를 나타냅니다.

priority_queue<int, vector<int>, less<int>> pq; // == priority_queue<int> pq;

// priority_queue<Template, Container, Comparer>

최대 힙을 이용한다면 Container, Comparer 부분을 생략해도 됩니다. less<int>는 비교연산 함수입니다. 첫번째 인자가 두번째 인자보다 크다면 true를 반환합니다. 즉, less<int>가 true인 경우를 기준으로 정렬하면 오름차순 정렬이 됩니다. less<int>는 다음과 코드와 같다고 볼 수 있습니다.

bool less(int a, int b){
    return a < b;
}

만일 최소 힙을 이용하는 우선순위 큐를 사용하고 싶다면 다음과같이 쓰면 됩니다.

priority_queue<int, vector<int>, greater<int>> pq;

greater<int> 함수는 less와 정반대의 동작을 합니다. 내림차순으로 정렬됩니다.

solution 함수에서는 0~k일 까지 루프를 돌립니다. 루프안의 지역변수 i는 현재 날짜에 해당합니다. idx는 공급받을 수 있는 날인 dates와 공급량인 supplies를 같이 참조하기위해 관리하는 인덱스 변수입니다. 매번 i와 dates[idx]와 비교하여 공급받을 수 있는 날이면 우선순위 큐에 받을 수 있는 수량을 넣습니다. 이렇게 되면 현재 날짜까지 받을 수 있는 모든 공급량을 우선순위 큐에서 가지고 있게 됩니다. 그다음 stock을 확인합니다. 만일 재고가 없다면 stock == 0 공급을 받습니다. pq.top()을 통해 우선순위 큐의 맨 앞에있는 자료를 가져옵니다. 이때 나오는 값은 우선순위가 가장 높은 (최대값) 공급량을 나타냅니다. 공급을 받았으면 pq.pop()으로 해당 값을 큐에서 지워야합니다. 공급을 받았으므로 answer를 1증가시켜주고 루프의 마지막에 하루가 지났으므로 stock을 1감소시켜줍니다.

우선순위 큐에대한 설명이 길었지만, 문제 자체는 그렇게 많은 코드가 필요하지 않았습니다. (STL의 힘) 사실 이 문제는 우선순위 큐를 어떤식으로 적용해야 하는가가 조금 어려운 문제였습니다.

Code

C++로 풀이한 참고용 코드입니다.

Github

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, less<int>> pq; // == priority_queue<int> pq;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0, idx = 0;

    for (int i = 0; i < k; i++) {
        if (idx < dates.size() && i == dates[idx]) {
            pq.push(supplies[idx]);
            idx++;
        }
        if (!pq.empty() && !stock) {
            stock += pq.top();
            pq.pop();
            answer++;
        }
        stock--;
    }

    return answer;
}

int main() {
    int stock = 4;
    vector<int> dates = { 4, 10, 15 };
    vector<int> supplies = { 20, 5, 10 };
    int k = 30;

    cout << solution(stock, dates, supplies, k);

    return 0;
}