27. 라면공장 ⁂

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

라면공장
힙(Heap) 
3174명 완료

저에게 Level2에서 가장 힘들었던 문제를 꼽으라면 가장 큰 수, 124 문제와 이 문제입니다. 
조이스틱(완전 탐색)도 오래 걸렸군요.. 

제가 푼 방식은 다음과 같습니다.  

1. 날자가 흘러가면서 스톡이 1씩 줄어들겠죠. 
2. 공급일이 되면 일단 공급을 '우선순위 큐'에 (임시로) 집어넣습니다. 
3. 시간이 지나 재고가 바닥이 되면 (stock == 0) (임시) 큐에 들어있는 가장 큰 공급을 뽑아서 스톡에 더 해줍니다. 
4. 3번의 횟수를 카운트합니다.

--------

먼저 공급을 큐에 넣었다가 바닥이 난 날짜에 뽑는 이유를 생각해 봅시다.  

실제 상황이 아닌 일종의 시뮬레이션이니까
"받았다고 해두고(=큐에 넣고)"
재고가 바닥나면
"어 그때 받았잖아 받은 거 쓰자. (=큐에서 꺼내기)"
라고 해도 문제가 없기 때문입니다. (횟수만 맞으면 되니깐요.)

이렇게 프로그래밍하는 것이
공급을 스톡에 넣어서 바닥을 확인하고
바닥이 안 나면 빼는 방식보다 효율적입니다.  

이때 최댓값(가장 큰 공급)을 뽑는 이유는 최소한의 횟수를 구해야 하기 때문이죠. (우선순위 큐)

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

파이썬

import heapq


def solution(stock, dates, supplies, k):
    answer = 0
    heap = []
    for i in range(1, k):
        if i in dates:
            temp = supplies[dates.index(i)]
            heapq.heappush(heap, (-temp, temp))
        stock -= 1
        if stock == 0:
            stock += heapq.heappop(heap)[1]
            answer += 1
    return answer

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.8MB)
테스트 2 〉	통과 (0.16ms, 10.7MB)
테스트 3 〉	통과 (0.07ms, 10.7MB)
테스트 4 〉	통과 (0.37ms, 10.7MB)
테스트 5 〉	통과 (0.35ms, 10.8MB)
테스트 6 〉	통과 (0.20ms, 10.7MB)
테스트 7 〉	통과 (0.31ms, 10.8MB)
테스트 8 〉	통과 (0.23ms, 10.6MB)
테스트 9 〉	통과 (0.17ms, 10.7MB)
테스트 10 〉	통과 (0.14ms, 10.6MB)
테스트 11 〉	통과 (0.05ms, 10.8MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)

힙 큐까지 동원했지만 효율성 테스트에서 실패했습니다. ㅠ,.ㅠ
(최댓값을 연속적으로 찾을 때는 힙 큐가 좋습니다. )
https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88

파이썬의 heapq 모듈

k까지 매일매일 확인하는 부분이 반복을 많이 만듭니다. 
공급일에만 체크하는 방식으로 바꿨습니다.
잘 안되네요.. 5번 테스트 케이스에서 걸립니다. ㅠ,.ㅠ 
질답란에서 같은 케이스가 있어서 테스트 케이스만 휘릭 뽑아옵니다. 

import heapq


def solution(stock, dates, supplies, k):
    answer = 0
    heap = []
    dates.append(k)
    for idx, day in enumerate(dates):
        if day < k:
            heapq.heappush(heap, (-supplies[idx], supplies[idx]))
            while stock - day <= 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
        elif day == k:  # else 라고 써도 될 것 같지만...
            while stock - day < 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
    return answer


print(solution(8, [5, 10], [5, 10], 15) == 2)  # false

테스트 케이스를 보니 문제가 뭔지 알겠네요. 

10일의 경우 stock이 이미 마이너스가 된 상태죠.
이때는 미리 '5일에 공급분을 썼다.' 라고 처리해야 하는데, 
코드를 보면 스탁에서 가장 큰 10일(당일) 공급분을 써버렸네요. 

케이스를 나눠서 공급 순서를 조절 해야겠습니다.
점점 코드가 산으로 갑니다. ㅠ,.ㅠ 

import heapq


def solution(stock, dates, supplies, k):
    answer = 0
    heap = []
    dates.append(k)
    for idx, day in enumerate(dates):
        if day < k:  
            if stock == day: # 당일 앵꼬가 난 경우, 힙에 공급 후 최대값을 찾아 스탁에 채움
                heapq.heappush(heap, (-supplies[idx], supplies[idx]))
                while stock - day <= 0:
                    stock += heapq.heappop(heap)[1]
                    answer += 1
            else: # 이미 앵꼬가 난 경우, 먼저 힙에서 최대값을 찾아 스탁을 채운 뒤 공급
                while stock - day <= 0: 
                    stock += heapq.heappop(heap)[1]
                    answer += 1
                heapq.heappush(heap, (-supplies[idx], supplies[idx]))
        elif day == k:  # 마지막 날은 정상 공급이 되기 때문에 수입이 필요 없습니다. 
            while stock - day < 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
    return answer

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.07ms, 10.6MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.7MB)
테스트 5 〉	통과 (0.08ms, 10.8MB)
테스트 6 〉	통과 (0.08ms, 10.7MB)
테스트 7 〉	통과 (0.08ms, 10.8MB)
테스트 8 〉	통과 (0.08ms, 10.7MB)
테스트 9 〉	통과 (0.07ms, 10.8MB)
테스트 10 〉	통과 (0.08ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.8MB)
효율성  테스트
테스트 1 〉	통과 (4.57ms, 22.2MB)
테스트 2 〉	통과 (3.67ms, 18.4MB)
테스트 3 〉	통과 (1.42ms, 11.7MB)

이중 if보다는 이렇게 정리하는 게 가독성이 좋지 않나요?

import heapq


def solution(stock, dates, supplies, k):
    answer = 0
    heap = []
    dates.append(k)
    for idx, day in enumerate(dates):
        if k > day != stock:
            while stock - day <= 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
            heapq.heappush(heap, (-supplies[idx], supplies[idx]))
        elif k > day == stock:
            heapq.heappush(heap, (-supplies[idx], supplies[idx]))
            while stock - day <= 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
        elif day == k:
            while stock - day < 0:
                stock += heapq.heappop(heap)[1]
                answer += 1
    return answer

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.07ms, 10.7MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.13ms, 10.8MB)
테스트 5 〉	통과 (0.09ms, 10.8MB)
테스트 6 〉	통과 (0.08ms, 10.9MB)
테스트 7 〉	통과 (0.09ms, 10.8MB)
테스트 8 〉	통과 (0.09ms, 10.8MB)
테스트 9 〉	통과 (0.07ms, 10.6MB)
테스트 10 〉	통과 (0.06ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
효율성  테스트
테스트 1 〉	통과 (4.77ms, 22.2MB)
테스트 2 〉	통과 (3.60ms, 18.2MB)
테스트 3 〉	통과 (1.50ms, 11.8MB)

풀고 나서 다른 분들의 깔끔한 코드를 보면... ㅠ,.ㅠ 
제 코드는 ... (그래도 제 코드가 꽤 빠릅니다.~~~!)