2019 KAKAO BLIND RECRUITMENT- 무지의 먹방 라이브, 파이썬

1. 문제

- 효율성 테스트에 부분점수가 있는 문제 = 효율성 테스트 통과가 관건

- 문제 자체는 이해하기 쉬운 편

2. 풀이 

- 효율성 통과를 못할걸 알았지만 일단 대강 짜서 정확성 테스트만 통과했다. 

- 효율성 테스트의 경우 k의 값이 이미 1억을 넘기기 때문에 k번 순회하는 것은 안 된다. 

- 배열에서 최소값을 찾아내야 하고 적절한 계산 후 pop()으로 빼줘야 하기 때문에 우선순위 큐가 떠오르긴 했다. 

- 다만 배열 길이를 줄여가면서 몫과 나머지로 처리하려는 계획이 너무 복잡해서 그냥 구글링을 해봤다.

- 조금 더 고민했으면 풀었을 것 같은데 너무 쉽게 포기한 감이 있다. 

 

- 맨 아래 코드는 구글링 한 코드를 참고하여 작성하였다. 

- 주의할 점은 heapq.heappop(heap)의 경우 heap이 비어있으면 IndexError가 발생한다. 이 부분 처리 주의

- prev를 활용하였는데 prev 말고 차감한 시간을 계속 더해줄 변수를 활용하여 푸는 것도 가능하다. 

- 핵심은 k를 하나하나가 아닌 뭉탱이로 줄여주는 것. 

 

3. 코드

def solution(food_times, k):
    answer = 0
    cnt = 0
    arr = []
    for i, food in enumerate(food_times) :
        arr.append([food, i])
    while arr :
        i = 0
        while i < len(arr):
            if cnt == k :
                return arr[i][1] + 1
            arr[i][0] -= 1
            cnt += 1
            if arr[i][0] == 0:
                del arr[i]
            else :
                i += 1
    return -1

효율성 고려, 우선순위 큐 활용

import heapq

def solution(food_times, k):
    answer = 0
    cnt = 0
    arr = []
    for i, food in enumerate(food_times) :
        arr.append([food, i])
    heapq.heapify(arr)
    min_time = arr[0][0]
    prev = 0
    while k - (min_time - prev) * len(arr) >= 0 :
        k -= (min_time - prev) * len(arr)
        prev= heapq.heappop(arr)[0]
        if not arr :
            return -1
        min_time = arr[0][0]
    arr.sort(key = lambda x : x[1])
    return arr[k % len(arr)][1] + 1