[그리디] 06.무지의 먹방 라이브 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

그리디 개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기
• 다양한 알고리즘에 두루 사용    # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

빈출유형

거스름돈 문제

• 거슬러 줘야 할 동전의 최소 개수 찾는 문제
• 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업

1이 될 때까지

• N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산
• 최대한 많이 나누기가 문제 해결 아이디어

 

문제

 

해설

시간이 적게 걸리는 음식부터 확인하는 탐욕적 접근 방식으로 해결

시간 기준으로 정렬한 후, 시간이 적게 걸리는 음식부터 제거

 

ex) 3개의 음식, K를 15초라고 하자

1번 8초 소요

2번 6초 소요

3번 4초 소요

 

0. 모든 음식을 우선순위 큐(최소 힙)에 삽입

K초 후에 먹어야 할 음식의 번호 출력 → (음식 시간, 음식 번호)의 튜플 삽입

• 전체 남은 시간(K) : 15초
• 남은 음식 : 3개
• 현재 우선순위 큐

 

1. 가장 적게 걸리는 3번 음식 빼기

단, 음식 3개 남아있으므로(1, 2, 3번 음식) 

3(남은 음식 종류) x 4(3번 음식 먹는 시간) = 12초 빼야 함

남은 시간 15 - 12 = 3초로 줄어듦

• 전체 남은 시간(K) : 3초
• 남은 음식 : 2개
• 먹은 음식 : (4, 3)
• 현재 우선순위 큐

 

2. 다음으로 적게 걸리는 2번 음식 빼기

이번에는 음식 2개 남아있으므로(1, 2번 음식)

2(남은 음식 종류) x 2(2번 음식 먹는 시간) = 4초, 잔여 시간 3초이므로 뺄 수 없음

'다음으로 먹어야 할' 음식의 번호를 찾아 출력

매초 먹어야 할 음식을 일렬로 나열하여 4번째 음식 번호 출력

• 전체 남은 시간(K) : 3초
• 남은 음식 : 2개

 

 

풀이

# 이 코드는 다음 프로그래머스 사이트에서 테스트해야 정상 동작
https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1
    
    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i+1))
        
    sum_value = 0               # 먹기 위해 사용한 시간
    previous = 0                # 직전에 다 먹은 음식 시간
    length = len(food_times)    # 남은 음식의 개수
    
    # sum_value + (현재 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1       # 다 먹은 음식 제외
        previous = now    # 이전 음식 시간 재설정
        
    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1])    # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

 

해석

변수 : 각 음식 소요시간(번호순) food_times, 방송 중단된 시간 k, 우선순위 큐 q, 섭취 수행 시간 sum_value,
          직전에 다 먹은 음식 시간 previous, 남은 음식 종류 length, 현재 음식 소요시간 now

 

1. 입력 초기 전체 음식 섭취시간 sum(food_times)가 방송 중단된 시간 k보다 작으면 -1

2. 우선순위 큐 q에 (음식 시간, 음식 번호) 삽입

3. sum_value, previous, 남은 음식 종류 수 length 초기화

-------------------- 반복문 : [ sum_value + ((q[0][0] - previous) * length) <= k ] --------------------

4. 현재 음식 소요시간 now 초기화

5. 섭취 수행 시간 sum_value 업데이트 : (now - previous) * length

6. 다 먹은 음식 제외 : length - 1

7. 이전 음식 시간 재설정

-----------------------------------------------------------------------------------------------------------------------

6. 남은 음식을 번호 기준으로 정렬