[프로그래머스] 라면공장

[프로그래머스] 라면공장

코딩테스트 연습 - 라면공장 | 프로그래머스

우선순위 큐를 사용하면 쉽게 풀 수 있는 문제였지만, 나느 전혀 생각하지 못하였다.

내가 처음에 생각했던 방식은 현재 재고에서 공급받을 수 있는 날짜 중 최댓값을 찾아내어 재고에 더해주는 방식이었는데 for문이 몇번이든 계속 돌아갈 수 있으니 시간초과도 일어나고 올바른 답도 아니었다.

 

우선순위 큐를 사용해서 푸는 방법은 공급받는 시점에서 보는 것이 아니라 재고가 부족한 시점에서 보는 것이다.

 

• day = 0일째 부터 k-1일 까지 날마다 stock을 소진시킨다.
• day가 dates[idx]와 같은 날짜일 때 우선순위 큐(pq)에 공급(supplies[idx])을 push를 해준다. idx도 증가시킨다.
• stock이 0이 된다면 공급량 중 최댓값을 우선순위 큐에서 가져와 더해준다.
• day가 k-1을 넘어가면 종료

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

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0;
	int idx = 0;
	priority_queue<int> pq;
	for(int i = 0; i < k; i++){
		if(i == dates[idx]){
			pq.push(supplies[idx++]);
		}
		if(stock == 0){
			stock += pq.top();
			pq.pop();
			answer += 1;
		}
		stock -= 1;
	}
    return answer;
}