무지의 먹방 라이브

2025-10-30

#JAVA#프로그래머스

3분

문제 링크

문제 풀이 시간 : 58분

문제 요약

•
food_times[i]는 각 음식을 먹는 데 걸리는 시간

•
한 번에 1초씩 먹으며, 1초가 지나면 다음 음식으로 넘어감

•
k초가 지나면 네트워크가 끊기는데, 그때 먹고 있던 음식 번호를 구해야 한다.

•
모든 음식을 다 먹었는데도 k초가 남으면 1을 반환

문제 풀이

처음에는 단순히 음식을 하나씩 먹어가면서 k를 줄여나가는 완전탐색 방식을 생각해봤다.

하지만 음식의 개수가 최대 20만 개까지 주어지기 때문에 이 방법은 효율성 테스트에서 절대 통과할 수 없다.

그래서 “한 번에 여러 음식을 처리할 수 있는 방법은 없을까?” 고민하다가

한 음식씩 1초씩 먹는 대신 한 사이클 전체를 한 번에 처리하는 방식으로 접근할 수 있다고 생각했다.

즉, 남은 음식이 len개라면, 현재 가장 적게 남은 음식(time)까지 한 번에 len * (time - 지난시간) 만큼 먹을 수 있다는 점에 착안했다.

이 아이디어를 코드로 옮기기 위해

음식들을 먹는 시간이 적은 순서로 정렬된 우선순위 큐에 넣었다.

이제 다음과 같은 방식으로 진행된다.

1
우선순위 큐에서 현재 가장 적게 남은 음식(now.time)을 꺼낸다.

2
이전 단계에서 소비한 시간(t)을 빼서, 남은 시간 차이(cur = now.time - t)를 구한다.

3
그 차이(cur) 동안 모든 음식을 한 바퀴 도는 데 걸리는 시간은 cur * len

4
만약 k가 그보다 크거나 같으면, 한 바퀴를 전부 돌 수 있다는 뜻
→ 해당 음식은 다 먹은 것이므로 큐에서 제거하고 k -= cur * len 처리.

5
그렇지 않다면, 그 시점에서 네트워크가 끊긴 것이므로 루프를 종료한다.

그 후, 남은 음식들을 인덱스 순으로 정렬하고,

k % 남은 음식 개수 번째 음식을 찾아서 반환한다.

핵심 로직

•
우선순위 큐: 음식 중 가장 빨리 사라질 음식을 빠르게 찾기 위함.

•
사이클 단위 계산: 매초마다 반복하지 않고, 한 번에 여러 초를 처리.

•
남은 음식 처리: 더 이상 한 사이클을 돌 수 없을 때, 남은 음식 배열을 인덱스 순으로 정렬해 위치 계산.

최종 코드

Java

import java.util.*;

class Solution {
    
    // 음식 정보를 담는 클래스 (먹는 시간, 인덱스)
    public class Food {
        public int time;  // 해당 음식을 먹는 데 걸리는 시간
        public int idx;   // 음식의 원래 인덱스
        
        public Food(int time, int idx){
            this.time = time;
            this.idx = idx;
        }
    }
    
    public int solution(int[] food_times, long k) {
        long len = food_times.length; // 남은 음식 개수
       
        // 먹는 시간이 짧은 순으로 정렬되는 우선순위 큐 생성
        PriorityQueue<Food> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.time == o2.time)
                return o1.idx - o2.idx; // 시간이 같으면 인덱스 순으로
            return o1.time - o2.time;   // 시간이 짧은 음식이 먼저
        });
        
        // 모든 음식을 큐에 넣기
        for (int i = 0; i < len; i++) {
            pq.add(new Food(food_times[i], i));
        }
        
        long t = 0; // 지금까지 소비된 '기준 시간'

        // 큐가 빌 때까지 반복
        while (!pq.isEmpty()) {
            Food now = pq.peek();        // 가장 적게 남은 음식
            long cur = now.time - t;     // 이전에 제거한 음식 기준으로 남은 시간 차이
            
            // cur * len : 남은 음식 전부를 한 바퀴 돌며 cur초씩 먹는 데 걸리는 총 시간
            if (cur * len <= k) {        
                // 아직 k 안에 다 먹을 수 있다면, 한 사이클 전부 먹기
                t = now.time;            // 이번 음식 시간만큼 기준 시간 갱신
                k -= cur * len;          // 그만큼의 시간 차감
                len--;                   // 한 음식 제거되므로 남은 음식 수 감소
                pq.poll();               // 실제로 음식 제거
                continue;
            }
            
            // 한 바퀴를 다 돌 수 없으면 현재 음식이 먹는 도중에 네트워크가 끊김
            break;
        }
        
        // 모든 음식을 다 먹은 경우 (-1 반환)
        if (pq.size() == 0)
            return -1;
        
        // 아직 남은 음식들을 배열로 옮기기
        Food[] remain = new Food[pq.size()];
        for (int i = 0; i < remain.length; i++) {
            remain[i] = pq.poll();
        }
        
        // 남은 음식들을 원래 인덱스 순서대로 정렬
        Arrays.sort(remain, new Comparator<Food>() {
            @Override
            public int compare(Food o1, Food o2) {
                return o1.idx - o2.idx;
            }
        });
        
        // k초 이후에 먹고 있을 음식의 위치 계산
        Long r = k % remain.length;   // 남은 음식 중 몇 번째인지
        
        // 인덱스 반환
        return remain[r.intValue()].idx + 1;
    }
}