[그리디] 무지의 먹방 라이브

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 ↑ (총 2시간 소요)

1. 문제 설명

- 무지가 먹방 회전 초밥집 같은 느낌으로 라이브를 찍으려고 하는데 서버가 터지는 경우가 있다. 이 때 서버가 터지면 먹던 것을 멈추고 서버가 다시 돌아왔을 때 멈춘 부분부터 먹어야 한다.  그러면 서버가 터진 이후 먹어야 하는 부분은 어디인가?

2. 접근 방식

- 처음에는 for문을 활용해 문제를 푸려고 했는데 테스트 케이스에서 반 이상 틀리는 것을 보고 접근 방향을 다시 잡고자 했다. (30분 소요)

- 주어진 k의 길이가 너무 길어서 문제인가 해서 리스트를 줄이고 하면 좋을 거라고 생각해 food_times의 길이로 K를 나눈 몫을 활용한 방법을 사용했는데, 방법은 참신했던 것 같으나 여전히 문제 통과가 안됐다.(50분 소요)

- 접근 방법을 바꿔 deque를 이용했는데 그제서야 테스트 케이스 통과가 됐다. 하지만 효율성 부분에서 계속 막혔다. (40분 소요)

- 결국 답을 보았고, 'heapq'를 활용해야 한다는 것을 알았다.  

3. 코드

1) for문 코드 (틀린 코드)

def solution(food_times, k):
    idx = 0
    for _ in range(k): # 시간
        if idx == len(food_times):
            idx = 0
        while True:
            if food_times[idx] == 0:
                idx+=1
                if idx == len(food_times):
                    idx = 0
            else:
                break
        food_times[idx] -= 1
        idx += 1
    if idx == len(food_times):
        idx = 0
    answer = idx+1
    return answer

2) deque 코드 (효율성 Fail)

from collections import deque

def solution(food_times, k):
    food_len = len(food_times)
   """
# food_times 어느정도 깍으려던 코드 (해답 코드에서는 더 간결하게 구현되어 있었다.
    roop = k // food_len
    remain = k % food_len
    count = 0
    food_times = list(map(lambda x: x-roop, food_times))
    minus = min(food_times)
    food_times = list(map(lambda x: x-(min(food_times)), food_times))
    print(food_times)
    roop = (-minus)
    k = (roop)*food_len + remain
   """    
    q = deque()
    for i, v in enumerate(food_times):
        if v != 0:
            q.append(i)
    for _ in range(k):
        if not q:
            break
        idx = q.popleft()
        food_times[idx] -= 1
        if food_times[idx] != 0:
            q.append(idx)
    answer = -1 if not q else q.popleft()+1
    return answer

3) 해답 코드

import heapq

def solution(food_times, k):
    if sum(food_times) <= k: # 전체 음식을 먹는 시간보다 k가 크거나 같으면 -1
        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) # 남은 음식의 개수
    
    # "먹기 위해 사용한 시간 + (현재 음식 시간 - 이전 음식 시간) * 현재 남은 음식 개수" 와 "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] # 반복문을 돌지는 않지만,

 

4. 코멘트

- deque나 heapq의 경우 둘 다 자료형이라는 것은 동일하지만 그 내부적으로 효율성이 다르다는 점을 기억하자.

- heapq까지 생각했었는데, heapq의 효율성이 더 좋다는 것을 잊었었던 것 같다. 

- 다양한 자료형과 시간복잡도에 대해 공부하는 것은 코딩테스트를 함에 있어서 큰 무기가 되는 것 같다. 다양한 모듈, 함수, 자료형 등을 기억할 필요가 있다.

- 해답 코드에서는 내가 생각했던 부분이 더 쉽고 압축되어 구현이 되어 있었다. 

- 또한 heapq의 특성 중 하나로, heapq로 push한 파라미터의 경우 [0]번째가 자동으로 최소값이 된다.