[프로그래머스 힙] 라면공장 - C++

https://programmers.co.kr/learn/courses/30/lessons/42629

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

우선순위 큐로 max heap을 구현해서 푸는 문제입니다.

이 문제에서 헷갈렸던 점은 공급받은 날짜와 상관없이 공급받은 양을 기준으로 max heap에 넣는 게 맞는지 였어요.

 

먼저, date를 계산하면서 stock을 하나씩 줄여가되, 해당 date에 공급받은 양을 우선순위 큐에 넣어야 합니다.

그렇게 되면 지금 공급을 받았더라도 이전에 공급받은 양보다 적으면 큐에서 pop할 때 우선순위에서 밀리게 돼요.

 

즉, 오늘 stock이 다 떨어졌다면 그 이전의 어떤 날에 공급받은 것 중 가장 공급이 많은 날의 공급을 택해서 보충합니다.

 

어차피 공급받는 횟수가 가장 적길 바라기 때문에 최대한 많이 받을 수 있는 날을 골라서 공급받으면 되기 때문이에요.

그 날 공급받았다고 그 날 바로 공급받은 만큼 stock을 충전해야 하는 게 아니란 겁니다.

전체적으로 마지막날까지 계산해 봤을 때 가장 적은 횟수로 공급받는 방식을 찾는 거예요.

 

문제 자체가 날짜를 셀 때 'k일째의 밀가루' 보다는 '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 di=0;
    priority_queue<int, vector<int>, less<int>>pq;
    for(int i=0; i<k;i++){
        if(di<dates.size() && dates[di]==i){
            pq.push(supplies[di]);
            di++;
        }
        if(stock==0){
            stock = stock + pq.top();
            pq.pop();
            answer++;
        }
         stock--;
    }
    return answer;
}

 

주석있는 코드

 

#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 di=0;//dates 의 index
    priority_queue<int, vector<int>, less<int>>pq;
    for(int i=0; i<k;i++){//0일후(오늘)부터 k-1일 후까지
        //공급받는 날엔 우선순위 큐에 넣기
        if(di<dates.size() && dates[di]==i){
            pq.push(supplies[di]);
            di++;
        }
        if(stock==0){
            stock = stock + pq.top();
            pq.pop();
            answer++;
        }
         stock--;
    }
    return answer;
}