무지의 먹방 라이브

무지의 먹방 라이브문제 보기

Level4

프로그래머스📅 2025-07-04

그리디우선순위 큐효율성시뮬레이션

문제 설명

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

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

무지는 다음과 같은 방법으로 음식을 섭취한다 :

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

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

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

제한사항

food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
k 는 방송이 중단된 시간을 나타낸다.
만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

food_times 의 길이는 1 이상 2,000 이하이다.
food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

food_times 의 길이는 1 이상 200,000 이하이다.
food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
k는 1 이상 2 × 10^13 이하의 자연수이다.

입출력 예

입력

food_times = [3, 1, 2], k = 5

출력

설명

0~1초 : 1번 음식 섭취. 남은 시간 [2,1,2]
1~2초 : 2번 음식 섭취. 남은 시간 [2,0,2]
2~3초 : 3번 음식 섭취. 남은 시간 [2,0,1]
3~4초 : 1번 음식 섭취. 남은 시간 [1,0,1]
4~5초 : 3번 음식 섭취. 남은 시간 [1,0,0]
5초에서 장애 발생 → 1번 음식부터 재시작

풀이 접근법

시간복잡도 : O(N log N)

공간복잡도 : O(N)

사용 알고리즘 :

우선순위 큐그리디시뮬레이션 최적화

핵심 포인트 :

K가 최대 2 × 10^13이므로 단순 시뮬레이션으로는 시간 초과
음식을 시간 순으로 정렬하여 라운드 단위로 처리
우선순위 큐를 사용하여 가장 빨리 끝나는 음식부터 처리
남은 음식들에 대해서만 최종 계산 수행

경계값/반례 :

모든 음식을 다 먹은 경우: -1 반환
K가 매우 큰 경우: 효율성 고려 필요
음식이 1개인 경우: 예외 처리

핵심 아이디어

k는 최대 2 × 10^13이므로 1초 단위로 확인하는 것은 불가능합니다. 묶어서 처리하는 최적화가 필요합니다.

해결 방법

객체로 (시간, 원본인덱스) 저장하여 정렬 후에도 원본 위치 추적
우선순위큐로 가장 적은 시간부터 처리
각 라운드마다 제거되는 시간 = (현재시간 - 이전시간) × 남은음식수
남은 시간으로 최종 음식 위치 계산

내부 해부 과정

food_times = {3, 1, 1, 5, 4}, k = 12

예제 풀이에 따라 테이블 순서에 따라 1초에 해당 순서의 음식을 1만큼 줄인다.
- 모든 음식을 1회만큼 섭취 시 ⇒ 1회전 : food_times.length = 5
- 각 음식의 필요 시간은 다 먹는데 걸리는 회전 수로 판단 가능하다.
⇒ food_times의 2, 3번째 음식은 1이므로 1회전 시 다 먹는다. 즉, 5초 뒤에 2, 3번째 음식은 없는 상태
다만 음식이 줄어들게 됨에 따라 1회전에 걸리는 시간의 수는 감소한다.
- 1번째 회전 시 제거되는 음식의 수 = 2개
- 1번째 회전 후 : 추가 1회전에 걸리는 시간 = 5 - 2 = 3초
- 1번째 회전 후 남은 시간 k = 12 - 5 = 7초
- 1번째 회전 후 배열 food_times = {2, 0, 0, 4, 3}
다음 2번째 회전 후
- 3초가 지난다. k = 7 - 3 = 4초
- 2번째 회전 시 제거되는 음식의 수 = 0개
- 2번째 회전 후 배열 food_times = {1, 0, 0, 3, 2}
- 다음 회전에 걸리는 시간 = 3초
다음 3번째 회전 후
- 3초가 지난다. k = 4 - 3 = 1초
- 3번째 회전 시 제거되는 음식의 수 = 1개
- 3번째 회전 후 배열 food_times = {0, 0, 0, 2, 1}
- 다음 회전에 걸리는 시간 = 2초
- 남은 시간에 비해 다음 회전에 걸리는 시간이 더 크므로 다음 회전 진행 중에 정전이 발생한다.
다음 4번째 회전 진행 중
- 1초가 지난다. 4번째 요소를 먹는다. food_times = {0, 0, 0, 1, 1} k=0 ⇒ 정전 발생
- 5번째 음식부터 다시 먹기 시작하면 된다.

생각 과정

회전에 걸리는 시간은 남아있는 음식의 수에 따라 달라진다.
즉, 남아 있는 것들 중 가장 시간이 작은 것이 제거되는 순간까지 동일하다.
회전의 수를 제거되는 순간까지 하나로 묶는다.
food_times = [3, 1, 1, 5, 4], k = 12
1회 처리 ⇒ 가장 작은 수 = 1 (2개 제거됨)
2회 처리 ⇒ 가장 작은 수 = 3 (1개 제거됨)
3회 처리 ⇒ 가장 작은 수 = 4 (1개 제거됨)
이때 걸리는 시간은 가장 작은 수의 시간 x 남아있는 요소(food_times.length)
1회 처리 ⇒ 1 x 5 = 5초
2회 처리 ⇒ 3 x (5-2) = 9초 ⇒ 5 + 9 = 14초
3회 처리 ⇒ 4 x (3-1) = 8초 ⇒ 14 + 8 = 22초
다만, 가장 작은 수의 시간은 이미 처리된 요소의 시간을 반영해야 한다.
1회 처리 ⇒ 1 x 5 = 5초 (k = 12 - 5 = 7)
2회 처리 ⇒ (3-1) x (5-2) = 6초 ⇒ 5 + 6 = 11초 (k = 7 - 6 = 1)
3회 처리 ⇒ (4-3) x (3-1) = 2초 ⇒ 11 + 2 = 13초 (k = 1 - 2 = -1)
4초가 걸리는 것을 처리하는 타이밍에 정전이 발생한다. (11 ~ 13초) 사이
2회 처리 후 ⇒ [3(0), 1(0), 1(0), 5(2), 4(1)], 11초 지남
1초가 지나면 12초 4번째 요소를 먹은 상태.
다시 돌아오면 5번째 요소를 먹으면 된다.
다시 처음으로 돌아가서
1. 가장 작은 수의 시간을 매 회 처리 시 구해야 한다.
  - 정렬이 필요하다. ⇒ 우선 순위 큐(내부적으로 정렬), 배열 정렬
  - 정렬 시 기존의 인덱스를 알 수 없다. ⇒ 원본 인덱스 저장 필요
2. 매 회 처리 시 해당 회차의 처리해야 하는 가장 작은 수의 시간은 현재 회차의 가장 작은 수 - 이전 회차의 가장 작은 수이다.
3. 매 회 처리 시 해당 회차의 처리해야 하는 요소의 수는 이전 회차의 남은 요소 수 - 이전 회차에서 제거된 요소 수이다.
4. 매회 처리 시 k의 값은
  k = 이전 회차의 k 값 - ((현재 회차의 가장 작은 수 - 이전 회차의 가장 작은 수) x (이전 회차의 남은 요소 수 - 이전 회차에서 제거된 요소 수))
  - k = 30, food_times = [4, 2, 3, 6, 7, 1, 5, 8]
  - 1회차 : k = 30 - ((1 - 0) x (8 - 0)) = 22
  - 2회차 : k = 22 - ((2 - 1) x (8 - 1)) = 15
  - 3회차 : k = 15 - ((3 - 2) x (7 - 1)) = 9
  - 4회차 : k = 9 - ((4 - 3) x (6 - 1)) = 4
  - 5회차 : k = 4 - ((5 - 4) x (5 - 1)) = 0 (회차가 다 끝났을 때 정전 발생)
  - 6회차, 즉 정전 이후엔 6번째로 큰값을 갖는 요소를 다 먹을 차례가 시작된다. ⇒ food_times에서 6번째로 큰 값은 배열의 3번 인덱스이다.
이렇게 처음에 정렬 시 원본을 알 수 있게 저장해둬야 하며, 결과를 보면 알 수 있듯 6번째로 큰 값을 찾아야 하고, 그 값의 원본 인덱스를 알아야 하며, 문제에서는 몇번째 음식부터 먹어야 하냐 물었으므로 0부터 시작하는 인덱스 형태가 아닌 1부터 시작하는 형태로 응답해야 한다.
- 즉, 원본 배열에서 해당 값과 인덱스를 유지해야 한다. ⇒ Map 또는 객체 저장
  - 인덱스는 요구하는 응답에 따라 배열 인덱스 + 1로 저장한다.
  - 이렇게 하면 원본을 다시 찾을 수 있다.
- 다만 Map의 경우 순서가 없기 때문에 힘들고 food_times를 객체화 하고 이를 정렬해야 한다.
  - k = 115 / food_times = {10, 35, 10, 20, 20, 24, 30, 30};
  - { Food(10, 1), Food(35, 2), Food(10, 3), Food(20, 4), Food(20, 5), Food(24, 6), Food(30, 7), Food(30, 8) }
  - 이를 시간 순서로 오름차순 정렬하면
  - { Food(10, 1), Food(10, 3), Food(20, 4), Food(20, 5), Food(24, 6), Food(30, 7), Food(30, 8), Food(35, 2) }
공식과 응용하면
- { Food(10, 1), Food(10, 3), Food(20, 4), Food(20, 5), Food(24, 6), Food(30, 7), Food(30, 8), Food(35, 2) }
- k = 이전 회차의 k 값 - ((현재 회차의 가장 작은 수 - 이전 회차의 가장 작은 수) x (이전 회차의 남은 요소 수 - 이전 회차에서 제거된 요소 수))
  기존의 공식의 회차는 시간 순서로 정렬했기 때문에 첫번째 요소가 1회차, 두번째 요소가 2회차 이런 형태로 진행된다. 다만 남은 시간을 통해 어떤 요소인지 특정할 때 기존의 것을 제거하면 쉬우므로 우선 순위큐를 이용해서 각 요소가 끝날 때마다 해당 요소를 제거해야 하고 남은 것들로 재정렬을 해야 순서대로 먹는 것을 파악할 수 있다.
  - k = 이전 회차의 k 값 - ((현재 요소 시간값 - 이전 요소의 시간값) x (제거 후 배열의 길이))
  - 1번 요소(Food(10, 1)) : k = 115 - ((10 - 0) x (8)) = 115 - 80 = 35 ⇒ 1번 제거
  - 2번 요소(Food(10, 3)) : k = 35 - ((10 - 10) x (7)) = 35 - 0 = 35 ⇒ 2번 제거
  - 3번 요소(Food(20, 4)) : k = 35 - ((20 - 10) x (6)) = 35 - 60 = -25
  - 2번 요소까지 제거된 뒤 3번째 시작하고 35초 뒤의 요소를 찾아야 한다.
    - { Food(20, 4), Food(20, 5), Food(24, 6), Food(30, 7), Food(30, 8), Food(35, 2) }
    - 재정렬 (원본 인덱스)
      - { Food(35, 2), Food(20, 4), Food(20, 5), Food(24, 6), Food(30, 7), Food(30, 8) }
      - 35를 6으로 나눈 나머지 = 5 ⇒ 즉, Food(30, 7)을 먹으면 정전 발생
    - 이후 정전이 끝나면 Food(30, 8)을 먹어야 하므로 8번째 음식을 먹어야 한다.

핵심 패턴

1️⃣ 데이터 클래스 활용

static class Food {
    int time;
    int originalIndex;

    Food(int time, int originalIndex) {
        this.time = time;
        this.originalIndex = originalIndex;
    }
}

// 객체로 변환하여 원본 인덱스 보존
for (int i = 0; i < food_times.length; i++) {
    foods.add(new Food(food_times[i], i + 1));
}

왜 필요? 정렬 후에도 원본 위치를 알아야 함
패턴 : 정렬이 필요하지만 원본 인덱스가 중요한 문제에서 자주 사용

2️⃣ 우선순위큐로 정렬 + 제거

// 시간 순으로 우선순위큐 생성
PriorityQueue<Food> foods = new PriorityQueue<>(Comparator.comparingInt(a -> a.time));

// 가장 적은 시간부터 처리하면서 제거
while (!foods.isEmpty()) {
    long currentTime = foods.peek().time;
    // ... 처리 후 제거
    foods.poll();
}

3️⃣ 시간 계산 공식

long removeTime = (currentTime - previousTime) * remainingFoods;

공식 : (현재 최소시간 - 이전 최소시간) × 남은 음식 개수
의미 : 현재 최소시간까지 모든 남은 음식을 먹는데 필요한 시간

4️⃣ 남은 시간으로 위치 찾기

// 원본 인덱스 순으로 재정렬
List<Food> foodList = new ArrayList<>(foods);
foodList.sort(Comparator.comparingInt(a -> a.originalIndex));

// 남은 시간으로 몇 번째 음식인지 계산
return foodList.get((int) (k % remainingFoods)).originalIndex;

최종 제출 코드

import java.util.*;

class Solution {
    
    static class Food {
        int time;
        int originalIndex;

        Food(int time, int originalIndex) {
          this.time = time;
          this.originalIndex = originalIndex;
        }
    }
    
    public int solution(int[] food_times, long k) {
        long totalTime = 0;
        for (int time : food_times) {
          totalTime += time;
        }

        if (totalTime <= k) return -1;

        PriorityQueue<Food> foods = new PriorityQueue<>(Comparator.comparingInt(a -> a.time));
        for (int i = 0; i < food_times.length; i++) {
          foods.add(new Food(food_times[i], i + 1));
        }

        long remainingFoods = food_times.length;
        long previousTime = 0;

        while (!foods.isEmpty()) {
          long currentTime = foods.peek().time;
          long removeTime = (currentTime - previousTime) * remainingFoods;

          if (removeTime <= k) {
            foods.poll();
            k -= removeTime;
            previousTime = currentTime;
            remainingFoods--;
          } else {
            break;
          }
        }

        List<Food> foodList = new ArrayList<>(foods);
        foodList.sort(Comparator.comparingInt(a -> a.originalIndex));

        return foodList.get((int) (k % remainingFoods)).originalIndex;
    }
}