[Algorithm] 무지의 먹방 라이브

풀이

 

1) 전제 조건 K 시간이 다 가기 전에 음식을 다 먹으면 -1을 반환한다.

food_times에 담긴 합이 K보다 작거나 같으면 -1을 반환한다.

 

2) 가장 적은 시간이 드는 음식 다 먹는 시간

현재까지 음식을 먹는데 걸린 시간 sum, 이전에 먹은 음식에 걸린 시간 pre 남은 음식 rest로 만들어진 식

sum + (pq.peek().getTime() - pre) * rest 은

이제 먹을 음식 pq.peek()을 먹는데 걸리는 시간에 pre를 빼는 것은 pre가 이미 sum에 합쳐져 있기 때문이다.

rest를 곱하는 이유는 pq.peek()을 먹으면 그만큼 다른 음식들도 먹어야 하기 때문이다.

 

위와 같은 식이 K보다 작을 경우 지금 먹는 음식을 모두 먹을 수 있다.

 

sum = 0; pre = 0; 인 상태에서 남은 음식의 수가 3개, 각각 2, 3, 4의 시간이 걸리고, K가 11인 상황을 가정한다.

가장 적은 시간이 걸리는 2 -> 2초가 3회, 6초의 시간이 걸린다. 11보다 작으므로 while문 실행된다.

 

sum = 6; pre = 6; 남은 음식의 수 2개, (3, 4)의 시간

가장 적은 시간이 걸리는 3 -> 3초가 2회 6초의 시간 11보다 크므로 넘어간다.

 

3) 남은 음식들로 남은 시간을 반복한다.

K에서 지금까지의 시간 sum을 빼면 5초의 시간이 남는다. 이 횟수 만큼 3초 음식과 4초 음식이 반복된다.

5 % 2 (k -sum) % rest을 통해 2개가 모두 반복되고도 1번 더 움직여야 한다. 이에 4초 음식이 선택되고 인스턴스를 참조해 Index를 반환한다.

 

import java.util.*;

class Food implements Comparable<Food>{
    private int index;
    private int time;
    
    public Food (int index, int time) {
        this.index = index;
        this.time = time;
    }
    
    public int getIndex() {
        return this.index;
    }
    
    public int getTime() {
        return this.time;
    }
    
    public int compareTo(Food other) {
        if (this.time < other.getTime()) {
            return -1;
        }
        return 1;
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        
        long sum = 0;
        for (int i = 0; i < food_times.length; i++) {
            sum += food_times[i];
        }
        if (sum <= k) return -1;
        
        // 먹는 시간이 적은 것부터 정렬된 우선순위 큐
        PriorityQueue<Food> pq = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            pq.offer(new Food(i+1, food_times[i]));
        }
        
        sum = 0; // 현재까지 먹는데 걸린 시간
        long pre = 0; // 이전에 먹은 시간
        long rest = food_times.length; //남은 음식의 수
        // pq.peek().getTime() - pre 지금 먹을 음식이 걸리는 시간
        // pre를 빼는 것이 이전에 먹은 음식시간 만큼은 이미 sum에 계산됨
        // rest를 곱하는 것은 지금 먹을 음식을 다 먹으면 나머지도 그만큼 1번씩 먹기 때문
        // 이전에 다 먹은 시간과 지금 먹을 것의 시간을 합쳤을 때 K보다 작다면 실행함.
        while (sum + ((pq.peek().getTime() - pre) * rest) <= k) {
            int now = pq.poll().getTime();
            sum += (now - pre) * rest--;
            pre = now;
        }
        
        List<Food> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.poll());
        }
        
        Collections.sort(list, (a, b) -> a.getIndex() - b.getIndex());
        
        int result = list.get((int)((k-sum) % rest)).getIndex();
        
        return result;
        
    }
}