알고리즘: 프로그래머스: 라면공장

참고

라면공장

자료구조: priority_queue

풀이 (1차)

  • stock에 남아있는 밀가루가 충분하다면, 현재 날짜까지 밀가루가 공급된 수량 중 큰 순서대로 공급하면 된다.
  • 큰 수량 부터 차례대로 받을 수 있는 자료구조가 필요하다.
  • 우선 순위 힙 (priority_queue) 를 사용한다.

  • priority_queue에는 supplies를 담는다.

풀이 (2차)

  • stock < istock <= i 로 수정
  • i 는 0일 부터 시작
  • 따라서 istock이 같을 때 밀가루 공급

#include <string>
#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> supplyPQueue;

	int j=0;
	for (int i=0; i<k; i++) {
		// 공급 받는 일정일 때, queue에 저장한다.
		if (i == dates[j]) {
			supplyPQueue.push(supplies[j]);
			j += 1;
		}

		// 저장된 stock 이 i보다 작아진다면
		// queue에 저장했던 밀가루를 pop
		if (stock <= i) {
			stock += supplyPQueue.top();
			supplyPQueue.pop();
			answer += 1;
		}
	}
	return answer;
}

코드

noodle.cpp