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

무지의 먹방 라이브

• 회전판에 N개의 음식이 있고 음식에는 1~N의 번호가 주어진다
• 음식은 전부 섭취하는데 일정 시간이 소요된다, food_times 배열에 들어있는시간
• 음식 하나를 1초동안 섭취하고 남은 음식은 남겨둔다
• k초 후에 먹어야 하는 음식을 리턴, 없으면 -1 리턴
• 1<=len(food_times)<=200,000
• 1<=food_times[n]<=100,000,000
• 1<= k <= 2 x 10^13

Solution

• 모든 음식을 먹는데 걸리는 총 시간과 k가
  같거나 큰 경우에는 불가능. -1 리턴
  if k >= sum(food_times) : return -1
• food_times를 (걸리는시간, 음식 번호)원소의 리스트로 변경
  food_times = [(val,i+1) for i,val in enumerate(food_times)]
• 먹는 시간이 가장 짧은 음식을 먹는데 t 시간이 걸리고, 음식 개수가 n개인 경우
• k > t * n 인 경우
  food_times 와 k가 다음인 경우와 결과가 동일
  food_times = [ (val-t, i) for val,i in food_times if val-t > 0 ]
  k = k - t * n
• k <= t * n 인 경우
  i = int(k%len(food_times))
  return food_times[i][1]
• 리스트의 각 요소에 t 시간을 빼는 대신 t를 변수에 저장
• 시간이 0이 된 요소를 제거한 list를 생성하는 대신
  시간 순으로 정렬한뒤, 시간이 짧은 음식부터 처리하고
  남은 음식의 개수를 갱신

Code1

def solution(food_times, k):

    # 전체 음식 용량이 k와 같거나 작은경우
    if k >= sum(food_times) : return -1

    # (시간,음식번호)
    food_times = [(val,i+1) for i,val in enumerate(food_times)]
    # 시간이 적게 걸리는 음식으로 sorting()
    food_times.sort()

    # 전체 음식 개수
    food_num = len(food_times)
    # 남은 음식 개수
    food_left = food_num

    # 전 단계에서 이미 소비된 시간을 중복해서 빼지 않기위한 변수
    base = 0

    for val, i in food_times:
        # skip 의 시간을 소요하면 val 시간이 걸리는 음식까지는 모두 먹은것으로 처리
        skip = (val - base) * food_left
        if k < skip : break

        k -= skip
        base = val
        food_left-=1

    food_times = food_times[food_num-food_left:].copy()
    food_times.sort(key=lambda x : x[1])
    idx = int(k%food_left)

    return food_times[idx][1]

Solution2

• 남은 시간이 가장 적은 음식을 가져올때, 우선순위 큐 자료구조를 사용할수 있음

Code2

import heapq

def solution(food_times, k):

    # 전체 음식 용량이 k와 같거나 작은경우
    if k >= sum(food_times) : return -1

    # (남은 시간,음식번호)
    food_times = [(val,i+1) for i,val in enumerate(food_times)]
    heapq.heapify(food_times)

    # 전체 음식 개수
    food_num = len(food_times)
    # 남은 음식 개수
    food_left = food_num        
    # 전 단계에서 이미 소비된 시간을 중복해서 빼지 않기위한 변수
    base = 0

    while True:
        skip = (food_times[0][0]-base) * food_left
        if k < skip : break                                    
        k -= skip
        base = heapq.heappop(food_times)[0]
        food_left-=1

    food_times.sort(key=lambda x : x[1])
    idx = int(k%food_left)

    return food_times[idx][1]

시간복잡도

• O(N) - sum
• O(N) - for
• O(N) - heapify
• O(NlogN) - while(heappop)
• O(NlogN) - sort