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

문제 <무지의 먹방 라이브>

회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
  • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
• 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.

---

입력

• food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
  • food_times 의 길이는 1 이상 200,000 이하이다.
  • food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
• k 는 방송이 중단된 시간을 나타낸다.
  • k는 1 이상 2 x 10^13 이하의 자연수이다.
• 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

출력

각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

---

풀이

• 남아있는 음식의 양과 음식 번호를 한 번에 확인할 수 있도록
• food라는 빈 리스트에 food_times[i]와 음식 번호 i+1을 리스트로 묶어 저장하였다.

• 음식이 남아있을 때 while 문이 돌아가도록 설정
  • 현재 음식의 개수를 lf에 저장
  • lf가 K의 값보다 작거나 같을 때
    • 남은 음식이 하나인 음식은 없애고, 각 음식의 양을 1 줄여 리스트에 저장
    • 음식의 개수만큼 K를 빼주기
  • 그렇지 않다면
    • K의 인덱스를 가지는 음식의 번호를 result에 저장
    • while 문 빠져 나옴

def solution(food_times, K):
    food = []
    l = len(food_times)
    result = -1
    for i in range(l):
        food.append([food_times[i], i+1])
    while food:
        lf = len(food)
        if lf <= K:
            food = [[a-1, b] for a, b in food if a != 1]
            K -= lf
        else:
            result = food[K][1]
            break
    return result

정확성 테스트 32개 전부 통과
효율성 테스트 8개 실패

효율성을 높이기 위한 방법 고려 -> 리스트 대신 우선순위 큐 사용

• 리스트 대신 heap을 이용해 시간 복잡도를 줄이기 위함

import heapq
def solution(food_times, K):
    food = []
    food_left = len(food_times)  # 남은 음식의 개수
    result = -1
    for i in range(food_left):
        heapq.heappush(food, (food_times[i], i+1))  # 튜플의 첫 번째 원소를 우선순위로 힙 구성
    ate = 0  # 직전에 먹은 음식의 양
    while food:  # 음식이 남아 있으면 while 문 진행
        t = (food[0][0] - ate) * food_left  # 현재 음식을 다 먹을 때까지 걸리는 시간
        if t <= K:  # 현재 음식을 다 먹을 수 있는 경우
            K -= t
            ate = heapq.heappop(food)[0]  # 현재 음식을 삭제하고 값을 반환
            food_left -= 1
        else:  # 현재 음식을 다 못 먹는 경우
            food.sort(key=lambda x: x[1])  # 음식 번호 순으로 정렬
            result = food[K % food_left][1]  # 먹어야 할 음식 구하기
            break
    return result

• food_times를 우선 순위 큐를 이용하여 food에 음식 번호와 함께 넣는다. (food_times, 음식 번호)

• 음식이 남아있을 때 돌아가는 while 문을 설정
• 남은 음식의 양이 가장 작은 음식부터 그 음식을 다 먹을 때까지 걸리는 시간을 t로 설정한다.
  • t = (현재 음식의 양 - 직전에 먹은 음식의 양) * 남은 음식의 개수
    • 현재 음식의 양은 직전 음식을 먹을 때 그 음식의 양만큼 작아지므로 (현재 - 직전)

• 현재 음식을 다 먹을 수 있는 경우
  • K의 값은 t를 빼서 갱신한다.
  • 직전에 먹은 음식의 양을 현재 먹은 음식의 양으로 갱신하고 삭제한다.
  • 남은 음식의 개수 -1

• 현재 음식을 다 먹을 수 없는 경우
  • 음식 번호 순으로 정렬
  • K가 남은 음식의 개수보다 클 수 있으므로 다음에 먹을 음식의 번호는 K % food 로 구한다.

정확성 테스트와 효율성 테스트 모두 통과.

---

큰 틀은 비슷하지만 숫자가 커질수록 리스트보다 heapq의 효율성이 커짐.

리스트와 우선순위 큐를 모두 사용할 수 있다면 시간 복잡도를 고려해 우선순위 큐를 사용하는 것이 좋음.

 

 

프로그래머스