4-9. 4주차 끝 & 숙제 설명 중 첫번째 농심 라면 공장 문제... - 인프런

1. 현재 학습 진도

몇 챕터/몇 강을 수강 중이신가요? 4-9 4주차 끝 & 숙제 설명
어떤 알고리즘을 학습하고 계신가요? 첫번째 문제 (라면공장)
여기까지 이해하신 내용은 무엇인가요? stock이라는 변수에, 날짜가 stock값보다 작은 date일 때의 supplies들 중 최대 값을 얻어서 다시 stock에 += 해주면서 최종적으로 stock이 k보다 커졌을 때 반복을 종료하고 결과값을 return하는 전반적인 알고리즘은 이해하였습니다.

2. 어려움을 겪는 부분

어느 부분에서 막히셨나요? 정답이 4가 나오는 예시 문제
코드의 어떤 로직이 이해가 안 되시나요? while stock <= k : 라는 반복문이 실행될 때 마다 max_heap을 왜 초기화시켜주지 않는 건가요? stock을 업데이트 하기 전에 남아있는 max_heap의 원소들과, stock을 업데이트 한 후에 새로이 추가된 max_heap의 원소들 중에 전자의 경우에서 max값이 나올 수 있기 때문인가요?
어떤 개념이 헷갈리시나요?

3. 시도해보신 내용

문제 해결을 위해 어떤 시도를 해보셨나요?
에러가 발생했다면 어떤 에러인가요? 가장 바깥의 while문에서 벗어나지 못하는 문제
현재 작성하신 코드를 공유해주세요

def get_minimum_count_of_overseas_supply(stock, dates, supplies, k): # 풀어보세요! max_coverd_date = 0 result = 0 remained_stock = stock max_coverd_date += remained_stock while max_coverd_date < k: #k일을 버틸 수 있을 때까진 반복해야 함 can_supplied_qty_list = [] while dates: supply_date = dates[0] if supply_date <= max_coverd_date: dates.pop(0) can_supplied_qty_list.append(supplies.pop(0)*-1) else: break if can_supplied_qty_list: heapq.heapify(can_supplied_qty_list) max_supplied_qty = heapq.heappop(can_supplied_qty_list)*-1 max_coverd_date += max_supplied_qty result += 1 return result

이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊

안녕하세요 가희님!! 좋은 질문 감사드립니다!

다음과 같이 답변드립니다

질문 1. while stock <= k 라는 반복문에서 max_heap을 왜 초기화하지 않나요?

max_heap을 초기화하지 않는 이유는, 이전에 추가된 공급량을 계속 활용하기 위해서입니다.
즉, stock을 업데이트하기 전에 들어온 공급량들과 이후에 새롭게 추가된 공급량들 중에서 최댓값을 뽑아야 하기 때문입니다.

좀 더 구체적으로 설명하면 문제의 핵심은 현재 stock으로 버틸 수 있는 날짜까지의 공급량을 우선순위 큐(최대 힙)에 넣고, 가장 큰 공급량을 먼저 사용하는 것입니다. stock을 업데이트한다고 해서 이전 공급량들이 쓸모없어지는 것이 아니라, 아직 사용되지 않았다면 언제든지 선택할 수 있어야 합니다.

따라서 이전 반복에서 추가한 공급량을 계속 유지해야 하므로, max_heap을 초기화하면 안 됩니다.

질문 2. max_heap에 있는 원소들과 새롭게 추가된 원소들 중 전자의 경우에서 max 값이 나올 수 있기 때문인가요?

네, 맞습니다!
이전 반복에서 max_heap에 추가된 공급량들 중에서 최댓값이 나올 수 있기 때문에, 새롭게 추가된 공급량들과 비교하여 여전히 가장 큰 값을 가져올 수 있어야 합니다.

get_minimum_count_of_overseas_supply(4, [4, 10, 15, 20], [20, 5, 10, 5], 40)

이 경우를 분석해보면:

현재 stock = 4
- 공급 가능 날짜: 4일 → 20 추가
- max_heap = [20]
- 가장 큰 값 20을 사용 → stock = 24
현재 stock = 24
- 공급 가능 날짜: 10일, 15일, 20일 → [5, 10, 5] 추가
- max_heap = [10, 5, 5]
- 가장 큰 값 10을 사용 → stock = 34
현재 stock = 34
- 공급 가능 날짜 없음
- max_heap = [5, 5]
- 가장 큰 값 5을 사용 → stock = 39
현재 stock = 39
- 공급 가능 날짜 없음
- max_heap = [5]
- 가장 큰 값 5을 사용 → stock = 44 → 목표 달성(k=40)

총 4번의 공급을 받았기 때문에, 정답은 4가 됩니다. 만약 max_heap을 초기화했다면, 이전 공급량들이 사라져서 선택할 수 없게 되고, 잘못된 결과가 나올 수 있습니다.

질문 3. while 문에서 벗어나지 못하는 문제

코드에서 무한 루프가 발생하는 이유는 max_heap이 비어 있는데 heappop을 시도했기 때문입니다.
즉, stock을 증가시키려고 하는데 추가할 공급량이 없어서 더 이상 진행할 수 없게 됩니다.

해결 방법

max_heap이 비어있을 경우, 더 이상 공급을 받을 수 없으므로 반복을 중단하는 조건을 추가하면 해결됩니다.

if not max_heap: 
  return -1 # 예외 처리 (공급을 받을 수 없는 경우)

이렇게 하면 더 이상 공급을 받을 수 없는 경우 즉시 종료할 수 있습니다.

인프런 커뮤니티 질문&답변

4-9. 4주차 끝 & 숙제 설명 중 첫번째 농심 라면 공장 문제 질문입니다.