[프로그래머스/알고리즘] 라면 공장

문제 설명

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

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

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

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

입출력 예 

stock : 4

dates :[4,10,15]

supplies : [20,5,10]

k : 30

return 2

해결 과정

제가 해결 했던 과정은 시뮬레이션처럼 0일부터 stock를 1개씩 계속 소비를 해서 30일까지 반복하는 과정이다.

n일 차에(dates)에 추가적으로 들어올 공급이 있다면 우선순위 큐를 이용해서 담아낸다. 우선순위 큐의 구조는 공급하는 양이 가장 많은 순으로 해야 stock이 부족할 때 가장 많이 받아야 최소한으로 공급받을 수 있기 때문이다.

c++에서 우선순위 큐는 priority_queue이고 템플릿 구조는 <내용 구조, 큐 구조, 정렬> 이렇게 되어있다. 나는 supplies를 담기 때문에 내용구조는 int이고 supplies의 구조는 배열이기 때문에 큐 구조를 vector<int>로 하고 정렬은 큰 순이 less<int>로 했다.

소스 코드가 어렵지 않으므로 그 외의 내용은 소스코드를 보고 확인하길 바랍니다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <functional> // less<int>사용하기 위한 헤더임
using namespace std;
priority_queue<int, vector<int>,less<int>> temp;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
 int answer = 0;
 int j = 0;
 for (int i = 0; i<k; i++) {
  if (dates[j] == i) {
   temp.push(supplies[j]);
   if (j != supplies.size() - 1)
    j++;
  }
  if (stock == 0)
  {
   stock += temp.top();
   temp.pop();
   answer++;
  }
  stock--;

 }
 return answer;
}