Programmers - 무지의 먹방 라이브 with JAVA

 

 

 

 

로직

우선, 큐에 [음식 양, 음식 번호] 를 넣고 음식양이 오름차순이 되도록 정렬한다.

예를 들어, [1, 2], [2, 3], [3, 1]이 있다고 가정하자.

 

- 처음 꺼낸 리스트는 [1, 2]가 된다.

- 음식양 1을 전체 리스트의 길이(3)만큼 먹는다. 하지만 1*3은 k보다 작으므로 더 진행

 

- 두번째 꺼낸 리스트는 [2, 3]이 된다.

- 전에 1만큼 먹었기 때문에 2-1 = 1이 된다.

- 음식양 1을 전체 리스트의 길이(2)만큼 먹는다. 그럼 지금까지 3 + 2를 먹었다. 이는 k와 같으므로 리스트를 다시 넣어주고 종료한다.

(지금까지 먹은양이 k보다 크다는 의미는 이번 음식이 없어지면서 또는 없어지기 전에 k만큼 먹었다고 할 수 있다.)

 

종료 시점에 리스트의 번호만 보면 [1, 3]이 남는다.

위 상황에서는 k만큼 먹고 다음 번호인 1을 출력한다.

 

 

 

주의 사항

우선 순위 큐 사용

- 처음에는 List에 담고 음식 양 순으로 정렬 -> 음식 번호 순으로 정렬해 답을 도출했다. 하지만 시간복잡도에 문제가 생긴다.

- 우선순위큐를 활용해 데이터를 넣고 마지막에 리스트로 만들어주고 한번만 정렬해 시간복잡도를 줄였다.

 

long 사용

- 음식의 값은 각 1000만까지 가질 수 있다. 따라서 음식의 합은 long처리를 해주어야 한다.

 

반환을 -1로 하는 경우

- 모든 음식의 양이 k보다 작거나 같다면 다음에 먹을 음식이 없으므로 -1을 반환해야 한다.

 

 

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] food_times, long k) {
        int len = food_times.length;
        long sum = 0;
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        for(int i=0; i<len; i++){
            queue.add(Arrays.asList(food_times[i], i+1));
            sum += food_times[i];
        }
        if(sum <= k){
            return -1;
        }
        long before_value = 0;
        long sum_value = 0;
        while(true){
            List<Integer> now = queue.poll();
            int now_value = now.get(0);
            if(sum_value + (now_value-before_value)*len >= k){
                queue.add(now);
                break;
            }
            sum_value += (now_value-before_value)*len;
            len -= 1;
            before_value = now_value;
        }
        List<List<Integer>> result = new ArrayList<>(queue);
        Collections.sort(result, Comparator.comparing(arr -> arr.get(1)));
        int index = (int)((k-sum_value)%len);
        return result.get(index).get(1);
    }
}