[프로그래머스 / C++] 라면공장 풀이

문제 설명

 

라면 공장에서는 하루에 밀가루를 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일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

 

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

코딩테스트 연습 - 라면공장

 

 

 

 

문제 풀이

 

stock이 0이되는 시점이 x일 후라고 가정하면, x일 이전에는 밀가루를 공급받아야 합니다. 따라서 dates 배열 내의 x일보다 작은 공급일 중에서 가장 공급량이 큰 날에 공급을 받으면 됩니다. 

 

코드에선 최대 공급량을 찾기 위해 최대 힙 우선순위 큐(pq)를 사용하였고, pq에 넣지 않은 공급일들 중 가장 빠른 날의 인덱스를 idx에 저장했습니다. 

 

 

다음과 같은 작업을 0일째 부터 (k-1)일째까지 반복수행(for문)합니다. 

 

1. 오늘 날짜가 idx가 가리키는 공급일과 같을 경우
   • pq에 공급량 저장
   • idx가 다음 공급일을 가리킴
2. stock을 다 썼을 경우 ( => 공급 받아야 함)
   • 가능한 제일 큰 공급량(pq.top())을 공급 받음
   • 공급 받은 날짜의 공급량 삭제(pq.pop())
   • answer에 1 더해주기
3. stock-- (매일 밀가루 1톤씩 소모)

 

 

 

소스코드

 

// 라면 공장
#include <iostream>
#include <vector>
#include <functional>
#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> > pq; // 최대힙을 만족하는 우선순위 큐
    int idx = 0; // pq에 넣지 않은 dates 중에서 가장 작은 것의 index
 
    for (int day = 0; day < k; day++) { // 0일째부터 (k-1)일째까지 반복
        if (dates[idx] == day) { // 공급받을 수 있는 날이 되었을 경우
            pq.push(supplies[idx]); // pq에 공급량 저장
            if (idx != dates.size() - 1) // dates 벡터 범위 넘어가는 것을 방지
                idx++; // 다음 공급일을 가리킴
        }
        if (stock == 0) { // stock을 다 썼을 경우
            stock += pq.top(); // 공급량이 제일 큰 날짜에 공급 받음
            pq.pop();
            answer++;
        }
        stock--;
    }
 
    return answer;
}

 

 

 

 

 

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