[이것이 코딩 테스트다 with Python] Chapter 11. 그리디 - 무지의 먹방 라이브

< 무지의 먹방 라이브 >

 

💬 문제 설명

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어졌고 고민 끝에 카카오 TV 라이브 방송을 하기로 마음먹었습니다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 다음과 같이 독특한 방식을 생각해냈습니다.

....

 

입력 (food_times)	입력(k)	출력(result)
[3, 1, 2]	5	1

💬 입력 조건

• food_times의 길이 ( 1 ≤ food_times ≤ 200,000 )
• food_times의 원소 ( 1 ≤ food_times ≤ 100,000,000 )
• k ( 1 ≤ k≤ 2 * 10의 13승 )

💬 출력 조건

• k초 후에 몇 번 음식부터 다시 섭취하면 되는지 출력

---

✍ 문제요약

무지가 먹어야할 음식이 food_times에 주어진다. 음식이 1초 한칸 씩 회전 한다고 했을 때, 무지는 첫 번째 음식을 먹기 시작해서 1초 뒤에 회전하여 자신의 앞에 오는 음식을 계속적으로 먹는다. 이 때 K초 후에 자신이 몇 번째의 음식을 먹게 되는지 구하여라.

💯 문제링크

프로그래머스의 "무지의 먹방 라이브"와 동일한 문제이다.

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

프로그래머스

 

---

✅  문제 풀이

1️⃣ 효율성 고려하지 않은 풀이

 

• 내용에서 주어진대로 프로그램을 작성했다.
• food_times 리스트에 주어진 음식의 수를 -1하고, 다음 음식으로 이동한다.
• 이것을 while문 안에서 k번 동작시켰다.
• 그 후에 변경된 food_times 리스트에서 다음으로 섭취해야 하는 음식의 번호, 음식이 없다면 -1을 출력했다.

def solution(food_times, k):

    SP = time = 0
    len_times = len(food_times)
    while time < k:
        SP %= len_times
        if food_times[SP]:                # 음식이 있으면
            food_times[SP] -= 1           # 음식을 섭취한다.
            time += 1                     # 음식을 섭취할 때만 +1초
        SP += 1                           # 음식의 번호를 의미하는 index값
    
    start = SP % len_times
    result = SP % len_times
    while not food_times[result]:         # 리스트에 음식이 없으면 
        result = (result + 1) % len_times # 가장 가까이에 위치한 음식을 찾아야함
        if start == result : break        # 원래 지점으로 돌아오면 음식이 없다는 의미
    
    result += 1
    if result - 1 == start and not food_times[result-1] : result = -1
    
    return result

<실행 결과>

 

 

 

• k가 최대 2 * 10의 13승이기 때문에 한번만 돌아도 시간이 오래 걸릴 수 있다.
• food_times 또한 길이가  최대 10의 9승이기 때문에 이것 또한 최대로 돌면 시간이 오래 걸릴 수 있다.
• 효율성을 고려한 풀이가 필요하다.

 

 

 

 

---

2️⃣ 효율성 고려한 풀이

 

• heap을 이용해서 음식의 번호와, 음식섭취 시간을 묶어서 h 리스트에 추가한다.
• 음식섭취 시간이 작은 것 부터 정렬해서 음식을 먹는다고 생각하자
• 3초의 섭취 시간이 걸리는 음식이 있다면, 이 음식을 다 먹는 동안 4초, 5초가 걸리는 음식의 경우 1초, 2초가 남게된다.
• [3, 1, 2]를 예시로 해보자
  
  
  • heap 자료 구조를 활용하여 내부 요소를 pop, push할 경우 자동으로 최솟값에 접근할 수 있다. ( 이해가 안되면 heap 자료구조 학습을 해보자 )
  • 위 예시의 경우 [섭취시간, 음식번호] 순으로 heap자료구조 생성 시, 다음과 같이 접근할 수 있다.
    

    

• 2번 음식의 섭취가 마무된 후의 모습을 보자
  
  
  • 음식을 회전시키며 섭취하기 때문에, 2번의 음식을 다 먹는 동안 1, 3 번 음식들도 시간이 흐른다.
  • 2번 음식의 섭취가 완료 되는동안, 총 3초의 시간이 흐른다.
  • 이렇게 하나의 음식을 섭취하는 동안 흐르는 총 시간이 k보다 작은 경우를 확인할 수 있다.
    
• 위 처럼 한 줄을 없애는 과정에서 k시간보다 크다면
  
  
  • k를 4라고 할 경우, 현재까지 섭취한 시간을 제외할 경우 섭취 예정이 더 오래 걸리게 된다.
  • 해당 문제는 음식을 주어진 순서대로 먹어야한다.
  • 한 줄을 전부 없애지 못하는 케이스는 이러한 규칙을 위배한다.
  • 음식 번호 순으로 정렬하여 남은 음식 섭취를 진행한다.
    

 

from heapq import heappop, heappush

def solution(food_times, k):
    h = []
    answer = -1
    
    for idx, time in enumerate(food_times,1):    # heap 만드는 과정
        heappush(h,(time,idx))
    
    foods_num = len(food_times)                  # 현재 남은 음식 수 
    food_time = 0                                # 직전에 다 먹은 음식의 섭취 시간
    
    while h:
        # h[0][0] 남은 음식 중 섭취 시간이 가장 적은 음식의 섭취 시간
        # food_time : 직전에 다 먹은 음식의 섭취 시간
     	# foods_num : 현재 남은 음식 수
     	# time = 하나의 음식먹는데 걸리는 총 시간
        
        time = (h[0][0] - food_time) * foods_num 
        
        if k >= time : 
            k -= time                            
            food_time, _ = heappop(h)            # 다 먹은 음식 제외
            foods_num -= 1                       # 갯수도 하나 줄이기
        
        else : 
            idx = k % foods_num                  
            h.sort(key = lambda x : x[1])        # 음식 번호순으로 정렬
            answer = h[idx][1]
            break
    
    return answer

<실행결과>