프로그래머스 문제 풀이 라면 공장

문제 URL 라면 공장

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도, 입력을 통해서 문제를 파악해보도록 하겠습니다. 문제의 입력은 이렇습니다.

 

입력:
stock = 4
dates = [4, 10, 15]
supplies = [20, 5, 10]
k = 30

 

문제에 따르면, 4일 째에 물량이 처음으로 동이 납니다.

 

4일 째
stock = 0 (4-4 (dates[0]))

 

그런데, dates 에는 4가 있습니다. 따라서 4일째, 물량인 20을 받습니다.

 

4일 째
stock = 20 (0 + 20 (supplies[0]))

 

이후, 우리는 10일 째, 15일 째 물량을 공급 받을 수 있습니다. 문제에 따르면, "최대한 적게 공급을 받는다"라고 적혀 있으니, 최대한 날짜를 뒤로 미룹시다. 따라서 15일째, 물량을 받는다고 합시다. 그럼 이렇게 될 겁니다.

 

15일 째
stock = 19(20 - 11 + 10)

 

이 경우, 물량을 더 안받고도 19일 더 버틸 수 있습니다. 즉 2번 공급받고 k인 30일 만큼 충분히 버틸 수 있다는 것이지요. 사람이 풀기에는 무지 쉬운 문제입니다. 그러나 프로그래밍적으로 풀면 쉽지가 않습니다. 자 이제 프로그래밍적으로 문제를 풀어봅시다.

 

"힙"파트에서 볼 수 있듯, 여기서는 힙/우선순위 큐를 이용해야 문제를 풀 수 있습니다. 여기서 중요한 점은 "stock을 빼지 않는다"입니다.

 

무슨 소리일까요? 다시 되짚어봅시다. 원래 물량이 4 있고, 4일째 물량 20을 받습니다. 이는, 24일동안 버틸 수 있음을 의미합니다.

 

그리고 24일 안에 10, 15 중 15일 물량 10을 받아서, 34일 간 버틸 수 있습니다. 즉, stock을 물량이 아니라, 버틸 수 있는 날짜로 보는 것입니다.

 

그렇다면, "최소로 공급받는다"라는 건 "내가 버틸 수 있는 날 안에서, 최대 공급량을 가진 날짜 순으로 공급 받는다".라는 전략으로 다시 쓸 수 있는 것이죠. 이제 살펴봅시다. 먼저 우선순위 큐를 하나 만들어둡니다.

 

pq = []

 

이제 stock 이 k보다 커질 때까지 다음을 반복합니다. 먼저 0일 ~ 4일(stock) 보다 작은 날짜 중에, 공급 날짜를 찾습니다.

 

pq = []
dates = [4, 10, 15] // 4일 선택
supplies = [20, 5, 10] //4일짜 물량 선택

 

4일밖에 없습니다. 그럼 우선 순위 큐에 4일차 물량을 저장합니다.

 

pq = [ 20 ]

 

이 저장된 물량을 다시 pq에서 뺴와서 stock에 더해줍니다.

 

pq = []
stock = 24 (20 + 4)
공급횟수 = 1

 

이제 다시, 4일보다 크고 24일보다 작은 날짜들 중 공급 날짜를 찾습니다.

 

pq = []
dates = [10, 15] // 10일 선택
supplies = [5, 10] //10일짜 물량 선택

 

먼저 10일이 있습니다. 물량 5를 pq에 저장합니다.

 

pq = [5]

 

근데 10일만이 역시 4일 ~ 24일 사이에 존재하는 공급 날짜일까요?

 

pq = [5]
dates = [10, 15] // 15일 선택
supplies = [5, 10] //15일짜 물량 선택

 

아닙니다. 15일 역시, 이 안에 있지요. 15일 물량 10 역시 우선순위 큐에 저장합니다.

 

pq = [10, 5]

 

이제 우선 순위 큐에서 가장 우선 순위가 높은 데이터를 뺴옵니다. 여기서 물량 크기가 큰게 우선 순위가 높습니다. 즉, 10을 stock에 더해줍니다.

 

pq = [5]
stock = 34 (24 + 10)
공급 횟수 = 2

 

이제 남은 버틸 수 있는 날짜 stock이 k보다 커졌으니 공급 횟수 2를 반환하면 됩니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. 최대 힙 기반의 우선순위 큐를 생성합니다.
2. stock이 k보다 작을 때까지 다음을 반복합니다.
   1. idx ~ dates의 끝까지 반복합니다.
      1. 만약 stock < dates[i]라면, 반복을 멈춥니다.
      2. 그 외에는 우선순위 큐에 supplies[i]를 넣습니다.
      3. idx를 i 바로 다음 인덱스로 옮깁니다.
   2. 우선순위 큐에서 데이터를 꺼내 stock에 더합니다.
   3. answer을 1 더합니다.

이를 코드로 표현하면 다음과 같습니다.

 

PYTHON 코드

def solution(stock, dates, supplies, k):
    import heapq
    
    answer = 0
    # 범위 시작점입니다.
    idx = 0
    # 1. 최대 힙 기반 우선순위 큐를 생성합니다.
    pq = []
    
    # 2. stock < k일 때까지 다음을 반복합니다.
    while stock < k:
        # 1. idx ~ dates의 끝까지 반복합니다.
        for i in range(idx, len(dates)):
            # 1. stock 이 dates[i]보다 작으면 반복을 멈춥니다.
            if stock < dates[i]:
                break
            # 2. 우선순위 큐에 supplies[i]를 넣습니다. 
            heapq.heappush(pq, -supplies[i])     
            # 3. 시작점을 i+1지점으로 옮깁니다.
            idx = i + 1

        # 2. 우선순위 큐에서 데이터를 꺼내 stock에 더해줍니다.   
        stock += (heapq.heappop(pq) * -1)
        # 3. 공급 횟수 answer에 1을 더해줍니다.
        answer += 1

    return answer

 

파이썬의 경우, "heapq"라는 표준 라이브러리를 이용하여, 문제를 풀어야합니다. 그러나 "heapq"는 최소 힙 기반의 라이브러리입니다. 최대 힙으로 이용하려면, -1을 곱해서 저장한 후, 꺼낼 때 다시 -1을 곱해주어야 합니다.

 

이번엔 CPP 코드입니다. 언어만 바뀐 것이지 알고리즘은 같습니다. 이 문제의 경우엔, CPP이 더 보기가 깔끔하네요.

 

CPP 코드

#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, vector<int>, less<int>> pq;
    
    while (stock < k) {
        for (int i = idx; i<dates.size() && stock >= dates[i]; i++) {
            pq.push(supplies[i]);
            idx = i + 1;
        }
        
        stock += pq.top();
        pq.pop();
        answer += 1;
    }
    
    return answer;
}