[이취코] 그리디-무지의 먹방 라이브(X)

해당 문제는 2019년 카카오 신입 공채 문제로 아래 링크에서 확인 가능합니다.

참고) 이것이 취업을 위한 코딩테스트다 with Python
Part3 그리디 알고리즘 - 무지의 먹방 라이브

이것이 취업을 위한 코딩테스트다 with Python GitHub

문제 풀이

food_times가 작은 순서대로 처리를 해야겠다고 생각은 했는데 자세한 풀이방법은 생각해내지 못했다. 그리고 우선순위 큐를 몰랐을 때는 단순하게 리스트 선언하고 반복문을 통해 튜플을 생성해서 리스트에 넣는 방식으로 했었는데 이번 기회에 우선순위 큐라는 것을 알게 되었고 효율적으로 코드를 작성할 수 있었다. 그리고 막상 풀이를 보고나니 생각한 것 보다 엄청 어렵지는 않았다...ㅎ

1. heap에 (food_time, 음식 번호)를 삽입한다.
2. food_time이 짧은 음식부터 음식을 먹는데 걸리는 시간을 계산한다.
   • 해당 음식을 먹는데 걸리는 시간 = 남은 음식의 양(시간) * 남은 음식 개수
   • 남은 음식의 양(시간): 현재 food_time - 이전에 제거한 음식의 food_time
3. 만약에 해당 음식을 다 먹을 수 있을 경우에는 음식을 heap에서 제거해버린다.
   • k에서 현재 음식을 먹는 시간을 뺀다.
   • 이전에 제거한 food_time과 남은 음식 개수를 재설정한다.
4. 해당 음식을 다 먹을 수 없는 경우에는 남은 음식 중에서 다음에 먹어야 할 음식 번호를 구한다.
   • heap에 남아있는 음식 번호 중에 k+1번째 번호를 찾는다.
     (예를 들어, K가 3이면 4번째 음식의 번호를 출력해야 함)
   • k는 남아 있는 음식 개수보다 클 수 있기 때문에 모듈러 연산을 한다.
     (k가 3이고 남은 음식이 4개이면 3 % 4 = 3)

구현 (책 + 외부풀이)

import heapq   # 우선순위 큐를 사용하기 위한 라이브러리

food_times = list(map(int, input().split()))
k = int(input())


def solution(food_times, k):
    hq = []
    fnum = len(food_times)   # 남은 음식의 개수
    answer = 0

    # 시간이 적게 걸리는 음식부터 빼야 하기 때문에 우선순위 큐 사용
    for i in range(fnum):
        heapq.heappush(hq, (food_times[i], i+1))

    previous = 0   # 이전에 제거한 음식의 food_time

    while hq:
        # 음식을 먹는데 걸리는 총 시간 = 남은 시간 * 남은 음식 개수
        time = (hq[0][0]-previous) * fnum

        # 시간이 남을 경우에는 우선순위 큐에서 현재 음식 빼기 (다먹음)
        if k >= time:
            k -= time   # 전체 시간에서 빼기
            previous = heapq.heappop(hq)[0]   # 이전 음식의 food_time 재설정
            fnum -= 1   # 다 먹은 음식 빼기
        # 시간이 부족할 경우(음식을 다 못먹을 경우) 남은 음식 중에 먹어야 할 음식 찾기
        else:
            idx = k % fnum
            hq.sort(key=lambda x: x[1])   # 번호 순으로 먹기 때문에 번호 순으로 정렬
            answer = hq[idx][1]   # 다시 먹어야 할 음식의 번호 출력
            break

    return answer


print(solution(food_times, k))

느낀점

그리디 알고리즘을 어느정도는 이해를 했다고 생각했는데 이 문제를 풀지 못하고 풀이를 보면서 아직 많이 모른다고 느꼈다. 앞으로도 계속해서 그리디 문제를 풀어보면서 조금 더 감을 익혀가도록 하려고 한다!

참고

https://mjmjmj98.tistory.com/149