무지의 먹방 라이브

https://tech.kakao.com/posts/355

✍️ 문제 요약

효율성 풀이가 까다로움. 이런 아이디어를 어떻게 떠올릴까?
K가 2 x 10^13 로 큼. 이런거를 계산과정에서 아예 예외시키는 방법으로 하는 풀이하는게 관건.
N은 200,000 이하.

💡 풀이 아이디어

어떻게 접근했는가?

먼저 음식별 필요 시간을 오름차순으로 정렬합니다. 시간의 오름차순으로 정렬해두면 음식을 먹는 데 소요되는 시간을 한꺼번에 지울 수 있습니다. 예를 들어 정렬한 시간이 T = [1, 3, 3, 4, 5]라면 처음에 T[0] * 5 = 5만큼의 시간을 한꺼번에 지울 수 있습니다. 다음으로 T[1]부터 남은 시간을 한꺼번에 제거합니다. 즉, (T[1] - T[0]) * 4 = 8 만큼의 시간을 한꺼번에 지웁니다. 마찬가지로 (T[2] - T[1]) * 3 = 0 만큼의 시간을 한꺼번에 지울 수 있습니다.

위와 같은 방법으로 시간을 지워가다가, 지운 시간의 합이 K 보다 커지게 되면 남은 시간의 개수로 나눈 나머지를 이용해 K 초 후 다시 먹기 시작해야 될 음식의 번호를 바로 구할 수 있습니다. 이때, 남은 시간을 다시 원래 음식의 번호 순서대로 재정렬해야 합니다.

핵심은 시간단위를 블록단위로 크게크게 해서 계산을 줄이는 것!

어떤 알고리즘/자료구조를 사용했는가?

그리디 기법
List

시간복잡도는?

O(N log N)

✅ 코드

import java.util.*;
 
class Solution {
 
    // 음식 정보를 담는 클래스 (시간, 원래 인덱스)
    static class Food implements Comparable<Food> {
        int time; // 남은 먹는 시간
        int idx;  // 음식 번호 (1-based)
 
        Food(int time, int idx) {
            this.time = time;
            this.idx = idx;
        }
 
        // 시간을 기준으로 오름차순 정렬
        @Override
        public int compareTo(Food other) {
            return this.time - other.time;
        }
    }
 
    public int solution(int[] food_times, long k) {
 
        // 1. 전체 음식을 먹는 시간보다 k가 크거나 같으면 -1 반환 (모든 음식을 다 먹는 경우)
        long totalTimeSum = 0;
        for (int time : food_times) {
            totalTimeSum += time;
        }
        if (totalTimeSum <= k) {
            return -1;
        }
 
        // 2. (시간, 인덱스) 쌍으로 리스트에 저장하고 시간 기준 오름차순 정렬
        //nlogn
        List<Food> foodList = new ArrayList<>();
        for (int i = 0; i < food_times.length; i++) {
            foodList.add(new Food(food_times[i], i + 1));
        }
        Collections.sort(foodList); // 시간 기준 오름차순 정렬
 
        // 3. 시간 블록 단위로 처리
        long timePassed = 0;       // 현재까지 소요된 총 시간
        int prevTime = 0;          // 이전 블록에서 다 먹은 음식의 시간
        int numFoods = food_times.length; // 현재 남은 음식의 개수
 
        for (int i = 0; i < foodList.size(); i++) {
            Food currentFood = foodList.get(i);
 
            // 현재 음식 시간과 이전 음식 시간의 차이 (이번 블록에서 각 음식당 먹는 시간)
            // 반드시 long으로 계산해야 함
            long timeDifference = (long)currentFood.time - prevTime;
 
            // 이번 블록에서 모든 남은 음식을 timeDifference 만큼 먹는데 걸리는 총 시간
            // (timeDifference가 0이면 같은 시간의 음식이므로 계산 불필요)
            if (timeDifference > 0) {
                long timeToEatThisBlock = timeDifference * numFoods; // long * int -> long
 
                // 만약 k가 이번 블록을 완료하기 전에 도달한다면
                if (k < timePassed + timeToEatThisBlock) {
                    // 남은 시간 (k - timePassed) 동안 몇 번째 음식을 먹어야 하는지 계산
                    long remainingK = k - timePassed;
                    // 현재 단계에서 남은 음식들(i번째 이후)을 원래 인덱스 순으로 정렬
                    List<Food> remainingFoods = foodList.subList(i, foodList.size());
                    remainingFoods.sort(Comparator.comparingInt(f -> f.idx)); // 인덱스 기준 오름차순
 
                    // remainingK를 남은 음식 개수(numFoods)로 나눈 나머지가 최종 음식의 순서
                    return remainingFoods.get((int)(remainingK % numFoods)).idx;
                }
 
                // 이번 블록을 다 먹어도 k에 도달하지 못하면 시간 누적
                timePassed += timeToEatThisBlock;
            }
 
            // 현재 음식을 다 먹었으므로, 남은 음식 개수 감소 및 이전 시간 업데이트
            numFoods--;
            prevTime = currentFood.time;
        }
 
        // 위 로직상 여기까지 도달하면 안되지만, 컴파일러를 위해 추가 (혹은 로직 오류 시 확인용)
        return -1;
    }
}

❌ 실패 or 오답 이유

소팅하자는 생각도 못함. 문제에서 원판으로 순서가 정해져 있다고해서 거기에 사고가 갇힘. 문제에서 요구하는게 뭔지 파악했으면 좀 수월했을거 같음. 문제는 어떤 요소에 대한 인덱스를 원하지 어떤 요소의 남은 시간을 원하지 않음.

📘 배운 점

K가 2 x 10^13 로 큼. 이런거를 계산과정에서 아예 예외시키는 방법으로 하는 풀이의 존재를 파악함.
List의 subList를 처음 써봄. 유용함.
소팅…

🪞 한 줄 회고

이번 문제를 통해 느낀 점, 나에게 하는 피드백 등

어렵다이거… 그래도 꾸준히 할 수 밖에 없다. 걍 하자.

Notes

Explorer