[코테 연습] 라면 공장 Python

문제 설명

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한사항

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

---

원트

def solution(stock, dates, supplies, k):
    info = list(zip(dates, supplies))

    cnt = 0
    while stock < k-1:
        info = [day for day in info if day[0] < stock+2]
        stock += info[-1][1]
        cnt += 1

    return cnt

 

무참히 실!패! 너무 간단하게 생각했나,,

date의 K보다 작은 값들의 하한을 구해서 계산하려 했다.

 

근데 좀 더 생각해보니 이렇게 하면 "최소"의 공급이라는 조건의 만족이 어렵다. 

 

가령 극한의 예를 보면 K가 30인데 stock이 4라고 해보자.  그럼 0,1,2,3일 쓰고 4일 째에 받아야 한다.

예를 들어 3일 째에 받을 수 있는게 26이고 4일 째에 받을 수 있는게 2개이고 6일 째에 받을 수 있는게 24라고 하자.

그럼 3일 째에 받았으면 한 번만 공급 받으면 되는데 무조건 하한으로 계산했기때문에 두 번의 공급이 이루어지는 멍청한 상황이 이루어진다.

 

멍청한 위지원...,,이 또,,

 

그러면 밀가루가 부족할 때 지금까지 받을 수 있었던 날 중 가장 많이 받을 수 있는 날짜로 정렬하면 되지 않을까?! 탐욕적인,,,  아,, 그 때가 좋았더라,, 하고

 

이트

힙큐 사용 ; 위에 생각한 대로 최대힙 사용해서 해봤다.  밀가루가 부족할 때 최대공급량을 취할 수 있도록

import heapq
def solution(stock, dates, supplies, k):
    if stock >= k or stock == k - 1:
        return 0

    candidates = []
    cnt = 0
    date_idx = 0
    for i in range(k - 1):
        if dates[date_idx] == i:
            if date_idx < len(dates)-1:
                heapq.heappush(candidates, (-supplies[date_idx], supplies[date_idx]))
                date_idx += 1
        if stock == 0:
            cnt += 1
            stock += heapq.heappop(candidates)[1]
        stock -= 1
    return cnt

정확성 테스트

테스트 1 〉	통과 (0.06ms, 10.7MB)
테스트 2 〉	통과 (0.12ms, 10.8MB)
테스트 3 〉	실패 (0.21ms, 10.8MB)
테스트 4 〉	통과 (0.10ms, 10.8MB)
테스트 5 〉	실패 (0.26ms, 10.8MB)
테스트 6 〉	통과 (0.08ms, 10.7MB)
테스트 7 〉	통과 (0.10ms, 10.9MB)
테스트 8 〉	통과 (0.09ms, 10.9MB)
테스트 9 〉	통과 (0.08ms, 10.8MB)
테스트 10 〉	통과 (0.08ms, 10.8MB)
테스트 11 〉	실패 (런타임 에러)

효율성 테스트

테스트 1 〉	통과 (5.95ms, 22.3MB)
테스트 2 〉	통과 (12.01ms, 18.2MB)
테스트 3 〉	실패 (시간 초과)

 

 

런타임 에러가 뜨는걸 보니 뭔가 idx 접근을 못한것도 있는거 같군,,

 

if date_idx < len(dates)-1:
                heapq.heappush(candidates, (-supplies[date_idx], supplies[date_idx]))
                date_idx += 1

 

이 부분이겠구나,, supplies 마지막에 접근을 못하게되겠군,, 그렇다고 len(dates)까지 하면 +=1을 할 수 없을 것이고,,  그럼 일단 꺼내고 만약에 len(dates)-1보다 작지 않으면 ++ 해야겠다.

 

런타임은 해결했지만그래도 실패가 뜬다.

다음과 같은 테스트 케이스를 추가했다.

stock = 1

dates = [1,2]

supplies = [1,2]

k = 2

답 = 1

stock이 1이므로 1일 째에 바로 공급을 받아야한다(0일부터 계산하니까)

그럼 1일날 받는데 1일날 supplies 보면 1을 받아서 써야한다. 내 코드 같은 경우 이런 경우에 답이 0이 나왔다.

문제 이해력이 모자랐다..

 

아래 부분을 넣어선 안됐다.  '0'일 부터 계산한다.에 어긋난다. 

그리고 두 번째에 for문을 k-1이 아니라 k까지 해야 맞는거였다.. ㅠ_ㅠ.. 

    if stock >= k or stock == k - 1:
        return 0
        
        
    for i in range(k):

 

하지만 이번엔 효율성에서 실패한다.  아래 코드인 len을 매 for문마다 체크하는 듯해서 len을 미리 상수로 받아놨다.

if date_idx < len(dates)-1:

전체 코드는 아래와 같다. 혹시 supplies의 idx로 접근하는 부분이 시간이 걸리나 싶어서 그것도 밖으로 한번에 구했다.

import heapq
def solution(stock, dates, supplies, k):
    candidates = []
    cnt = 0
    date_idx = 0
    length = len(dates)

    for i in range(k):
        if dates[date_idx] == i:
            supply = supplies[date_idx]
            heapq.heappush(candidates, (-supply, supply))
            if date_idx < length-1:
                date_idx += 1

        if stock == 0:
            cnt += 1
            stock += heapq.heappop(candidates)[1]
        stock -= 1

    return cnt

정확성 테스트

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.07ms, 10.8MB)
테스트 3 〉	통과 (0.06ms, 10.7MB)
테스트 4 〉	통과 (0.11ms, 10.8MB)
테스트 5 〉	통과 (0.10ms, 10.7MB)
테스트 6 〉	통과 (0.08ms, 10.8MB)
테스트 7 〉	통과 (0.10ms, 10.7MB)
테스트 8 〉	통과 (0.09ms, 10.8MB)
테스트 9 〉	통과 (0.09ms, 10.8MB)
테스트 10 〉	통과 (0.07ms, 10.8MB)
테스트 11 〉	통과 (0.05ms, 10.7MB)

효율성 테스트

테스트 1 〉	통과 (5.34ms, 22.3MB)
테스트 2 〉	통과 (11.46ms, 18.2MB)
테스트 3 〉	실패 (시간 초과)

 

효율성 하나가 통과했지만 마지막 효율성이 여전히 안되었다. 무엇이 또 시간을 걸리게 하는 것일까?

 

결국 다른 분의 코드를 봐따ㅠㅠ

 

https://codedrive.tistory.com/82

[Programmers]Lv 2. 라면공장

 

아! 혹시 굳이 k까지 갈 필요가 없는데 k까지 가는 for문이 문제인것이였나보다.

아래와 같이 굳이 다 찾을 필요없게  stock을 기준으로 while문을 돌렸다. 

• dates 리스트를 돌아다닐 idx를 따로 선언하여 이미 후보군으로 찾았던 dates는 제외하고 시작했다.
• else : break를 사용하여 for문이 다 돌지 않도록 주의하게했다. ( 중요! )

import heapq
def solution(stock, dates, supplies, k):
    candidates = []
    cnt = 0
    dates_idx = 0

    while stock < k:
        #공급일 후보 찾기
        for i in range(dates_idx, len(dates)):
            if dates[i] <= stock:# 현재 가진 stock으로 버틸 수 있는 최대 날짜를 찾음
                supply = supplies[i]
                heapq.heappush(candidates, (-supply, supply))
                dates_idx = i+1
            else:
                break
                
        cnt += 1 #이전까지 공급받을 수 있던 후보들중 공급자를 찾는다.
        stock += heapq.heappop(candidates)[1]

    return cnt

 

 

 

흑흑 또 남의 코드 봤어 ㅠㅠ 

 

하지만 오늘 알게된 것은 쓸때없이 for문이 끝까지 돌아가지 않도록 주의하자 ! 
len()과 같은 함수가 for문 돌때마다 실행되게 하지 않도록 하자!