[이코테-그리디] 기출 - 06.무지의 먹방 라이브

 

[문제]

https://programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

 

---

 

[정확성 통과, 효율성 실패 풀이] - 본인 풀이

🔎 아이디어

• 가장 쉽게 떠오를 수 있는 방법은 문제의 입출력 예시를 코드로 구현하는 것이다. 

 

🔎 코드 설계

• K초가 모든 음식을 먹는데 필요한 시간보다 크거나 같으면 애초에 K초 동안 모든 음식을 먹을 수 있다. 따라서 이를 확인해 조건이 만족되면 바로 -1을 반환한다.
• K초가 점점 줄어들면서 시간이 남아 있는 음식이면 먹고, 음식의 남은 시간을 변경한다.
• 그리고 다음으로 먹을 음식 번호를 찾는다.

음식 번호를 찾을 때 남은 시간이 0이 아닌 번호를 찾는다.다음 음식 번호는 (현재 음식 번호 + 1) 인데, (현재 음식 번호 + 1)이 음식 수를 초과할 수 있다.
따라서 (현재 음식 번호 + 1)를 음식 수로 나눈 나머지가 다음 음식 번호이다. 

• K초가 0이될 때까지 위 과정을 반복한다.   

def idx(food_times, food_num, food_idx):
    # 남은 시간이 0이 아닌 음식 번호를 찾을 때까지 반복
    while True:
        # 다음 음식 번호는 (현재 음식 번호 + 1) 
        # 그런데 (현재 음식 번호 + 1)이 음식 수를 초과할 경우도 있다
        # 따라서 음식 수로 나눈 나머지가 다음 음식 번호
        food_idx = (food_idx + 1) % food_num
        if food_times[food_idx] != 0:
            return food_idx

def solution(food_times, k):
    food_idx = 0
    time = k 
    food_num = len(food_times)
    food_time_sum = sum(food_times)

    # k초 동안 모든 음식을 충분히 먹을 수 있다.
    if k >= food_time_sum:
        return -1
    
    while(time): # time이 줄어들면서 음식 먹음 
      if food_times[food_idx] != 0:
            # 시간이 남아 있는 음식이면 먹음. 시간 줄어듦    
            time -=1
            food_times[food_idx] -= 1
      # 다음으로 먹을 음식 번호 찾기
      food_idx = idx(food_times, food_num, food_idx)

    # 코드에서는 인덱스 번호를 0부터 설정했으므로 1을 더한다
    return food_idx + 1

 

🔎 단점

• 정확성 테스트 제한사항에서 K는 1이상 2,000,000 이하의 자연수 이지만, 효율성 테스트 제한사항에서 K가 1이상 2 × 10^13 이하의 자연수이다.
• 위의 코드는 시간복잡도가 적어도 O(K)이므로 효율성 테스트에서 실패하게 된다.
• 시간 효율성을 통과하기 위해서 K초를 한 번에 줄이는 아래 방법을 사용한다. 

 

---

 

[성공 풀이] - 유튜브 ezsw님 풀이

🔎 아이디어

https://www.youtube.com/watch?v=zpz8SMzwiHM  ezsw님의 풀이 영상을 참고했다.

• 음식을 먹는데 걸리는 시간 순으로 정렬해서 시간이 적게 걸리는 음식부터 다먹는 것을 고려한다.
• 그 음식을 다먹었을 때 걸리는 시간을 구해 K에서 뺌으로써 K시간을 확 줄여나간다.
• 다먹는데 걸리는 시간이 현재 남은 시간 K보다 클 경우, 남은 음식들을 번호 순으로 다시 정렬하고, 남은 시간 K에 따른 최종 결과를 구한다.
• food_times = [3, 5, 1, 6, 5, 3], k=20 인 예를 들어보자

 

1. 아래 표는 음식 번호에 따른 음식을 먹는데 걸리는 시간을 나타낸다. 왼쪽의 food_times를 오른쪽과 같이 오름차순 정렬한다.

 

2. 3번 음식을 다 먹고 돌아오는데 걸리는 시간은 그림과 같이 1 × 6 = 6 이다. 따라서 남은 시간 K = 20 - 6 = 14 이다. 

3. 1번 음식을 다먹을려면 남은 음식들 만큼 두 바퀴를 돌면된다. 즉 1번 음식을 다먹는데 걸리는 시간은 아래 그림과 같이 2 (1번 시간 - 3번 시간)  × 5 (남은 음식 수) = 10 이다.  남은 시간 K = 14 - 10 = 4 가 된다.

 

4. 6번은 1번을 다 먹는동안 다 먹게 된다. 그래서 6번을 다 먹는 시간은 0이다. 남은 시간 K는 그대로 4이다.

5. 2번 음식을 다먹는데 걸리는 시간은 아래 그림과 같이 2 (2번 시간 - 6번 시간)  × 3 (남은 음식 수) = 6 이다. 그런데 남은 시간 K는 4이므로 6번을 다 먹을 수 없다.

6. '음식을 다 먹는데 걸리는 시간 > 남은 시간' 이 되는 경우에는 남은 음식을 번호 순으로 다시 정렬 한다.  2 -> 4 -> 5 순이 된다.  남은 시간 K는 4이므로 방송이 정상화 된 후 섭취해야하는 음식은 4번이된다. (2->4->5->2->4)

 

🔎 코드 

# 최악의 경우 음식의 수만큼만 roop를 돌면 되므로 시간복잡도가 줄어든다.
from operator import itemgetter

def solution(food_times, k):
  foods = [] # (먹는데 걸리는 시간, 음식 번호) 저장
  n = len(food_times) # 음식의 수
  for i in range(n):
    foods.append((food_times[i], i+1))
    
  # 튜플의 첫번째 인덱스 기준으로 정렬(걸리는 시간이 작은 음식부터 큰 음식순으로 정렬)
  foods.sort() 
  pretime = 0
  for i, food in enumerate(foods): # 음식을 먹는 roop
    diff = food[0] - pretime
    if diff != 0:
      spend = diff * n # 현재 음식을 다먹는데 걸리는 시간
      if spend <= k:
        k -= spend 
        pretime = food[0]
      else:
        idx = k % n # 여기서 n은 남은 음식의 수이다
        # 남은 음식을 번호 순으로 다시 정렬
        sublist = sorted(foods[i:], key=itemgetter(1)) 
        return sublist[idx][1]

    n -= 1 # 현재 음식 다 먹음
  # for문 도중 return이 안됬다는 것은 k가 남았다 
  # -> 음식을 다 먹었다 -> -1 반환  
  return -1