[2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브

문제

• 회전판에 N개의 음식이 있고, 음식을 섭취하는데 일정 시간이 소요된다.
• 1번부터 1초 동안 섭취한 후 다음 음식을 섭취한다. 회전판은 음식을 번호 순서대로 돌아간다.
• 먹방을 시작한지 K초 후, 몇 번 음식을 먹어야 하는지 구하기
• 더 섭취해야 할 음식이 없다면 -1 반환한다.

 

• 정확성 테스트
  1 <= 음식 개수 <= 2000
  1 <= 각 음식을 먹는데 걸리는 시간 <= 1000
  1 <= K <= 2,000,000

 

• 효율성 테스트
  1 <= 음식 개수 <= 200,000
  1 <= 각 음식을 먹는데 걸리는 시간 <= 100,000,000
  1 <= K <= 2 x 10^13

 

풀이 1

• K를 1초씩 넘겨가면서 음식을 찾는건 비효율적이다. -> 시간초과
• 넘길 수 있는 부분
  -> 다 먹는데 제일 적게 걸리는 음식의 시간이 10초라고 한다면, 음식 개수 * 10초 만큼은 무조건 필요하다.

def solution(food_times, k):
    # 예외 처리 - 다 먹는 경우
    if sum(food_times) <= k :
        return -1
    
    n = len(food_times)             # 음식 개수
    food_times = sorted([(food_times[i], i+1) for i in range(n)], reverse=True)
    prev = 0                        # 이전 시간 기록
    
    # 먹는데 걸리는 시간이 적은 음식부터 순서대로 회전판 한 바퀴를 돌며 음식 먹기
    while k >= n * (food_times[-1][0]-prev) :
        now, idx = food_times.pop() # (먹는데 걸리는 시간, 음식 번호)
        k -= n * (now-prev)         
        n -= 1
        prev = now
    
    # 남은 음식을 번호 순으로 정렬 후 다음 먹을 음식 구하기
    food_times.sort(key=lambda x: x[1])
    return food_times[k % n][1]

 

 

풀이 2

• 힙으로 풀기

import heapq

def solution(food_times, k):    
    if sum(food_times) <= k :
        return -1
    
    heap = []
    for i, x in enumerate(food_times):
        heapq.heappush(heap, (x, i+1))
    
    sum_value = 0
    previous = 0
    n = len(food_times)
    
    while sum_value + (heap[0][0] - previous) * n <= k :
        now = heapq.heappop(heap)[0]
        sum_value += (now - previous) * n
        n -= 1
        previous = now
    
    result = sorted(heap, key=lambda x: x[1])
    return result[(k-sum_value) % n][1]