[pro] 프로그래머스 level4 42891 무지의 먹방 라이브 (Java) - 시뮬레이션

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

[풀이]

food_times의 모든 음식을 먹는데 걸리는 시간이 k초 이상이라면 네트워크 장애 발생 이후 다시 먹을 음식이 없으므로 -1을 반환하도록 한다.

 

우선순위큐를 이용하여 음식을 먹는데 걸리는 시간 오름차순으로 Food를 빼올 수 있게 한다.

시간이 가장 적게 걸리는 음식을 다 먹을 수 있다면 더 오래 걸리는 음식들 역시 그 시간동안 먹게되므로 초가 감소될 것이다. 

이를 이용해서 k와 근접한 시간이 이내에 다 먹을 수 있는 음식을 모두 pq에서 제거할 수 있다.

음식을 다 먹는데 현재까지 걸린 시간 + (현재 음식을 먹는데 걸리는 시간 * 현재 남아있는 음식 수) <= k 라면 현재 음식을 모두 다 먹어 pq에서 없앨 수 있다는 의미이다. 따라서 음식을 먹는데 걸리는 전체 시간을 갱신해주고, 남은 음식 수를 줄여준다. 또한 다음 음식에 대해서 현재 음식을 먹는데 걸리는 시간만큼 감소시켜줘야 하므로 이를 prev_time에 저장해준다.

 

반복문이 종료되면 남아있는 음식에 한해서 k에 대한 계산을 해주면 된다. 음식들을 index 순으로 정렬해주고 남은 시간이 지난 후 음식의 인덱스를 반환해준다.

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        //몇 번 음식부터 다시 섭취하면 되는지 return
        
        long sum = 0;
        for(int i=0; i<food_times.length; i++){
            sum += (long)food_times[i];
        }
        if(sum <= k) return -1; //모든 음식을 다 먹음
        
        PriorityQueue<Food> pq = new PriorityQueue<>();
        int len = food_times.length;
        for(int i=0; i<len; i++){
            pq.add(new Food(i+1, food_times[i]));
        }
        
        long total_time = 0;
        long prev_time = 0;

        while(total_time + (pq.peek().time-prev_time)*len <= k){
            int curr = pq.poll().time;
            total_time += (curr-prev_time)*len;
            len -= 1;
            prev_time =  curr;
        }
        
        //index 순 정렬
        List<Food> list = new ArrayList<>();
        while(!pq.isEmpty()){
            list.add(pq.poll());
        }
        
        Collections.sort(list, new Comparator<Food>(){
            @Override
            public int compare(Food o1, Food o2){
                return Integer.compare(o1.idx, o2.idx);
            }
        });
        
        
        return list.get((int)((k-total_time)%len)).idx;  
        
    }
    
    static class Food implements Comparable<Food>{
        int idx;
        int time;
        Food(int idx, int time){
            this.idx = idx;
            this.time = time;
        }
        
        @Override
        public int compareTo(Food o){
            return Integer.compare(this.time, o.time);
        }
    }
}