(프로그래머스) 무지의 먹방 라이브 [java]

 

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

🐢 설명

제각각 양이 다른 음식들이 있을 때 주어진 시간 k까지 1초에 하나씩 먹게 되고 k때 정전이 일어나면 그 이후에 먹어야 되는 음식의 번호를 구하는 문제이다.

 

생각해보자. 음식의 양이 9 3 5 7 1 씩 있을 때, 5번음식을 먹기 위해서는 5번의 이동이 필요하다. 한바퀴를 돌기 위해서 5번 이동해야 하므로. 그리고 난 후 3번 음식을 다 먹기 위해서는 9 3 5 7 1 -> 8 2 4 6이 되어있고 총 8번의 이동이 필요하다.

 

이렇게 생각하면 음식의 양이 가장 낮은 순으로 정렬하고, [(현재 음식과 직전 음식의 양 차이) * 현재 있는 음식의 개수]는 현재 가지고 있는 음식의 구성을 깨트리지 않고 이동을 할 수 있는 최대값이 된다.

그림처럼 양이 1인 음식은 move가 5이내 까지는 포함해서 먹을 수 있게 되고, 그 이후에는 LEN을 1줄여서 양이 1인 음식을 빼줘야한다. 이때 이동횟수는 1 * 5이므로 k -= 5가 되겠다.

 

이후 양이 3인 음식은 move가 높이(2) * 음식 가지수 (4) 인 8 이내까지는 포함해서 먹을 수 있게 된다.

• 만약 k가 8보다 크거나 같다면, k -= 8을하고 빼버리고, 음식 종류를 줄이면 된다.
• 만약 k가 8보다 작다면, 현재 음식 종류 내에서 방송중단이 발생한다는 의미이므로 (남은 먹기 회수) k % (남은 음식 종류) LEN을 통해 몇번째 음식을 먹어야 하는지 알 수 있다.

🐢코드

import java.util.*;

class Solution {

    static ArrayList<Food> foodList = new ArrayList<>();
    static PriorityQueue<Food> pq = new PriorityQueue<>(Comparator.comparingLong(f -> f.time));
    static int LEN;

    public int solution(int[] food_times, long k) {

        LEN = food_times.length;

        for (int i = 0; i < food_times.length; i++) {
            pq.add(new Food(i + 1, food_times[i]));
        }

        long beforeFoodTime = 0;

        while (!pq.isEmpty())
        {
            Food nowFood = pq.peek();
            long diff = nowFood.time - beforeFoodTime;

            if (diff != 0)
            {
                long spendTime = diff * LEN;

                if (spendTime <= k) {
                    k -= spendTime;
                    beforeFoodTime = nowFood.time;
                }
                else {
                    foodList.addAll(pq);
                    Collections.sort(foodList, Comparator.comparingInt(f -> f.index));

                    return foodList.get((int)(k % LEN)).index;
                }
            }

            pq.poll();
            LEN--;
        }
        return -1;
    }

    private static class Food
    {
        int index;
        long time;

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

🐢 마무리