[프로그래머스] 무지의 먹방 라이브 - JAVA

[문제]

• 2019 KAKAO BLIND RECRUITMENT 문제
• 프로그래머스 level4

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

코딩테스트 연습 - 무지의 먹방 라이브

 

[풀이]

처음에 문제를 보면 아마 당연하게 k시간만큼 loop문을 돌면서 매초 순회하는 풀이가 떠오를 것이다. 

하지만 1초마다 순회하면 효율성에서 떨어진다. 시간을 한번에 벌크하게 계산할 수 있는 방법을 떠올려야 하는 문제다. 

 

핵심 아이디어는 다음과 같다. 

예시로 주어진 food_times = [3, 1, 2], k = 5 을 예시로 들어보자. 

가로가 음식 순서, 세로가 먹는 시간으로 하여 왼쪽 그림처럼 표현해보자. 한칸씩 숫자를 세며 위로 올라가면 k=5일 때 첫번째 순서 음식이 답이다. 왼쪽 그림은 한칸씩 숫자를 세야만 정답을 할 수 있다. 

 

오른쪽은 시간을 벌크하게 셀 수 있다.

왼쪽 그림을 시간을 기준으로 오름차순 정렬한다.

 

그러면 아래와 같이 3초, 2초씩 묶어서 시간을 셀 수 있다. 

 

저세한 설명은 아래 영상을 보면 된다!

<참고 영상>

https://www.youtube.com/watch?v=4MWxAt4fx5I 

 

 

[코드]

package kakao.blind2019;

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 무지의 먹방 라이브
 */
public class Test02 {
    public static void main(String[] args) {
        int[] food_times = {3, 5, 1, 6, 5, 3};
        //  {3, 1, 2};
        long k =
                //    5;
                20;

        int answer = solution(food_times, k);
        System.out.println(answer);
    }

    public static class Food {
        int order; // 몇번째 음식인지
        int time; // 먹는데 필요한 시간

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

    public static int solution(int[] food_times, long k) {
        List<Food> foodList = new LinkedList<>();
        for (int i = 0; i < food_times.length; i++) {
            foodList.add(new Food(i + 1, food_times[i]));
        }
        Collections.sort(foodList, Comparator.comparingInt(o -> o.time));

        int i = 0; // foodList의 현재 인덱스
        int foodCnt = foodList.size(); // 남아있는 음식 개수
        int preTime = 0;
        for (Food food : foodList) {
            long diff = food.time - preTime;
            if (diff > 0) {
                long spend = diff * foodCnt;
                if (k - spend >= 0) {
                    k -= spend;
                    preTime = food.time;
                } else {
                    k = k % foodCnt;
                    foodList.subList(i, foodList.size()).sort(Comparator.comparingInt(o -> o.order));
                    return foodList.get(i + (int) k).order;
                }
            }
            i++;
            foodCnt--;
        }
        return -1;
    }
}