[프로그래머스] 42891. 무지의 먹방 라이브

문제 링크

[프로그래머스] 42891. 무지의 먹방 라이브

풀이 과정

시간 효율성 측면을 생각해봐야 하는 문제입니다.

위와 같은 예시에서, 매 경과 초마다 음식의 섭취 시간은 위와 같이 감소하지만, 루프를 덜 돌며, 결과를 조금 더 빨리 구할 수 있는 방법을 생각해봐야 합니다.

가장 적은 섭취 시간을 갖는 음식을 가능한 한 빨리 없애는 것이 시간적인 효율성을 극대화하는 방법입니다. 우선순위 큐를 활용하여 섭취 시간을 오름차순으로 정렬해 두고, 음식을 하나씩 없애가며 경과 시간을 비교해봅니다.

먼저 food_times 요소들을 모두 우선순위 큐에 넣어줍니다. 우선순위 큐는 배열 타입을 가지며, 0번 째 요소는 섭취 시간, 1번 째 요소는 인덱스를 의미합니다.

경과 시간을 누적시키는 변수 sum 을 하나 정해두고, 이 sum 변수에 큐의 맨 앞 요소를 더했을 때 값이 k를 초과하는 지 확인합니다. k와 값을 비교하는 과정은 음식의 섭취 시간을 0으로 만들어 버려, 더이상 고려하지 않으려는 의도입니다. 큐에서 맨 앞 요소는 시간 내에 섭취를 다 할 수 있으므로(=결과적으로 섭취 시간이 0으로 설정되므로) 빠르게 걸러냅니다.

위 값이 k 이하이면 해당 음식은 큐에서 삭제시키고, k를 초과하면 해당 음식부터 남은 음식들은 일일이 세봐야 하는 시점이 됩니다.

비교는 sum + (pq.peek()[0] - prev) * pq.size() ≤ k 을 통해 실행됩니다. 예를 들어, 섭취 시간 4를 0으로 만들기 위해서는 네 번의 루프가 필요합니다. 즉, 자기 차례가 네 번 돌아와야 해당 음식은 다 먹은 상태가 됩니다. 또한, 큐에서 요소를 제거한다는 뜻은, 시간이 경과되었음을 의미하고, 큐에 남아있는 다른 요소들도 이를 알고 있어야 합니다. 따라서, 큐에서 요소를 삭제할 때는 직전에 삭제한 음식의 섭취 시간을 기억해두고, 해당 섭취 시간을 빼주어야 합니다

방금 전에 섭취시간 4 짜리 음식을 제거하면서 4번의 루프가 돌았기 때문에, 맨 앞 요소 [6, 1] 음식은 섭취를 네 번 했을테니, 남은 섭취 시간은 6 - 4 = 2 가 됩니다. 따라서, 기존 sum 에 (6 - 4) * 2 를 더하면 이번에는 k 값을 초과하게 되고, 이 말의 뜻은 완전히 제거해버리지 못하니까, 남은 시간에 맞춰 두 음식들을 놓고 인덱스를 확인해보라는 의미가 됩니다.

while (sum + (pq.peek()[0] - prev) * pq.size() <= k) {
    sum += (pq.peek()[0] - prev) * pq.size();
    prev = pq.peek()[0];
    pq.poll();
}

설명을 옮긴 코드는 위와 같습니다. 맨 앞 음식을 제거할 수 있는 시간 범위 안에 들어온다면, 해당 음식은 poll 해서 빼버리고 sum 을 누적시키고, prev 를 갱신해주고, pq 에서 해당 맨 앞 음식을 뽑아내줍니다.

ArrayList<int[]> list = new ArrayList<>(pq);
Collections.sort(list, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[1] - o2[1];
    }
});

return list.get((int) ((k - sum) % list.size()))[1] + 1;

이후, 우선순위 큐에 남은 음식들을 리스트로 옮겨준 뒤, 인덱스를 기준으로 정렬해줍니다. 문제에서 구해야 하는 k 초 후에 어느 음식을 섭취할 지는, 경과 시간 sum 을 고려해 그 인덱스를 찾아서 리턴해줍니다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static long solution(int[] food_times, long k) {
        long sum = 0;
        long prev = 0;

        for (int time : food_times) sum += time;

        if (sum <= k) return -1;

        sum = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        for (int i = 0; i < food_times.length; i++) {
            pq.add(new int[]{food_times[i], i});
        }

        while (sum + (pq.peek()[0] - prev) * pq.size() <= k) {
            sum += (pq.peek()[0] - prev) * pq.size();
            prev = pq.peek()[0];
            pq.poll();
        }

        ArrayList<int[]> list = new ArrayList<>(pq);
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        return list.get((int) ((k - sum) % list.size()))[1] + 1;
    }

    public static void main(String[] args) {
        solution(new int[]{3, 1, 2}, 5);
//        solution(new int[]{8, 6, 4}, 15);
    }
}