문제

링크

복습 요망!!

풀이

1. 먼저 음식의 총 섭취량이 K보다 작거나 같으면 -1 반환. (문제 조건이다.)

2. 첫 번째 음식 섭취한다. 시간은 1초 지남, 첫 번째 음식은 하나 줄어듬. --> 이렇게 순차적으로 먹방을 진행한다.

3. 순차적으로 음식을 섭취 후 K초 장애가 발생할 때 다음 음식이 무엇인지 체크 후 반환.

저는 위와 같은 풀이 방법을 생각하였다. 즉 순차적으로 완전탐색을 진행하여 K + 1초일 때 먹어야하는 음식을 찾으려 했다. 하지만 틀린 방법이였다...

이 문제는 효율성 테스트 제한 사항도 있다. 주어진 K의 조건이 1 <= K <= 2 * 10^13 이하의 자연수이므로 시간초과의 문제를 발생하게 되는 점을 간과했다... (완전 탐색 X)

다른 사람들의 풀이 방법을 본 후 학습한 내용을 간략하게 적어보았다. (아직까지도 이해가 잘 되지 않는다...)

1. 먼저 음식의 총 섭취량이 K보다 작거나 같으면 -1 반환. (문제 조건이다.)

2. 우선순위 큐를 이용하여 음식 먹는 시간이 적게 걸리는 것부터(음식량이 적은 순서부터) 큐에 삽입.
   (음식량이 적은 것을 다 먹게 된다면 어차피 그 보다 음식량이 큰 것들도 이미 다 먹은 음식만큼 먹게 되는 점을 이용했다.)

3. 음식을 다 먹은 시간과 앞으로 남은 음식을 먹을 시간이 K보다 작거나 같다면 현재 음식을 먹을 수 있는 것이므로 while문에서 total에 현재 먹는 음식 * 먹을 수 있는 음식만큼 더해준다.

4. 그러면 음식량이 적은 것은 다 먹었으며 먹을 수 있는 음식의 개수는 -1 해주고, 현재 먹는 음식의 시간을 저장.

5. while문의 조건을 탈출하면 해당 음식들을 index 순서대로 정렬.

6. 남은 음식 중 남은 K만큼의 index 번호를 반환.

즉 우리가 알고 싶은 것은 K초 근처의 값들이기 때문에 K초 전까지는 먹방을 진행하되 한번에 빠르게 넘어가고, K초 근처의 값들을 계산하자라고 생각하면 된다.

코드

import java.util.*;

class Food implements Comparable<Food> {

    // 음식의 시간 & 순서
    int time;
    int idx;

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

    // compareTo 메소드
    @Override
    public int compareTo(Food other) {
        return Integer.compare(this.time, other.time);
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        long food_sum = 0;  // 모든 음식 먹는데 걸리는 총 시간
        for (int i = 0; i < food_times.length; i++) {
            food_sum += food_times[i];
        }

        if (food_sum <= k) return -1;

        // (음식 시간, 순서) 쌍으로 우선순위 큐에 저장
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            pq.offer(new Food(food_times[i], i + 1));
        }

        long total = 0;   // 먹기 위해 사용한 시간
        long previous = 0;  // 직전에 다 먹은 음식 시간
        long length = food_times.length;    // 남은 음식 개수

        while (total + ((pq.peek().time - previous) * length) <= k) {
            int now = pq.poll().time;
            total += (now - previous) * length;
            length -= 1;
            previous = now;
        }

        ArrayList<Food> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }

        Collections.sort(result, new Comparator<Food>() {
            @Override
            public int compare(Food a, Food b) {
                return Integer.compare(a.idx, b.idx);
            }
        });

        return result.get((int) ((k - total) % length)).idx;
    }
}

참조 : https://jhhj424.tistory.com/34