[2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브

2019 KAKAO BLIND RECRUITMENT 무지의 먹방 라이브

유형

• 우선순위 큐 (Priority Queue)

코드

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

class Solution {
    class Food implements Comparable<Food> {
        int index;
        int time;

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

        // time 순별로 정렬
        @Override
        public int compareTo(Food other) {
            return Integer.compare(this.time, other.time);
        }
    }

    public int solution(int[] food_times, long k) {
        // food_times는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열
        // k는 방송이 중단된 시간을 나타낸다.
        int answer = 0;
        long allFoodEatingTime = 0;

        // 우선순위 큐에 Time을 기준으로 오름차순으로 정렬 -> 먹는데 시간이 덜 걸리는 음식 순으로 정렬됨
        PriorityQueue<Food> foods = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            foods.add(new Food(i + 1, food_times[i]));
            allFoodEatingTime += food_times[i];
        }

        // 더 섭취해야 할 음식이 없다면 -1을 반환
        if(allFoodEatingTime <= k) return -1;

        
        long totalTime = 0;     // 음식을 먹으면서 누적된 시간
        int foodLeft = foods.size();    // 남아 있는 음식의 개수
        int loopNum = 1;        // 남아있는 전체 음식을 다 먹는 루프를 몇 번 돌았는지
        
        while(totalTime + foodLeft <= k) {
            totalTime += foodLeft;
            while (foods.peek().time == loopNum) {
                foods.poll();
                foodLeft--;
            }
            loopNum++;
        }

        int findIndex = (int) (k - totalTime);
        // 남아있는 음식들을 index 순으로 다시 정렬
        List<Food> foodsSortedByIndex = foods.stream().sorted(new Comparator<Food>() {
            @Override
            public int compare(Food o1, Food o2) {
                return Integer.compare(o1.index, o2.index);
            }
        }).collect(Collectors.toList());
        answer = foodsSortedByIndex.get(findIndex).index;

        return answer;
    }
}

참고: https://moonsbeen.tistory.com/m/371