무지의 먹방 라이브 - '2019 카카오 코딩 테스트'

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

회전 초밥과 같은 회전판의 음식들이 제공되고, 무지가 1초마다 해당 음식들을 먹으면서, 음식들이 회전 합니다. 다 먹은 음식은 건너 뛰고, k 초가 주어지고, 음식을 먹기 시작하고, k초 후의 먹을 음식을 출력하는 문제 입니다. k가 굉장히 크므로, k를 기준으로 완전 탐색 하면, 시간 초과로 효율성 테스트에서 탈락 합니다. 따라서, food_times는 200,000으로 food_times를 완전 탐색 하면서 풀수 있는 방법을 찾아야 합니다.

 

 

1. 접근

1. 시간 별로 food_times를 정렬 합니다.

2. (현재 먹는 음식 시간 - 이전 먹은 음식 시간) x (남은 음식의 갯수) < 방송이 중단 될 시간(k)

3. 까지는 음식을 먹으면서 방송이 중단 될 시간(k => afterStopSec) 값을 업데이트 한다.

4. (현재 먹는 음식 시간 - 이전 먹은 음식 시간) x (남은 음식의 갯수) < 방송이 중단 될 시간(afterStopSec)

5. 이후에는 남아 있는 음식중 가장 적게 걸리는 음식의 시간이 afterStopSec 초 보다 오래 걸리 므로, 먹는 중간의 시간이 0이 되는 음식은 없다.

6. 따라서, afterStopSec % curLength 의 음식을 출력 시켜 줍니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Page316_3 {

    //https://programmers.co.kr/learn/courses/30/lessons/42891
    public static void main(String[] args) {
        int[] food_times = {3, 1, 2};
        long k = 5;
        System.out.print(new Page316_3().solution(food_times, k));
    }

    public int solution(int[] food_times, long k) {
        List<Food> foodList = new ArrayList<>();
        int id = 0;

        for (int food : food_times) {
            foodList.add(new Food(food, ++id));
        }

        // 먹는 시간별로 정렬
        foodList.sort(new CompTimes());

        long afterStopSec = k;
        int curLength = food_times.length;
        int curId = 0;
        int answer = -1;
        int eatenFoodTimes = 0;

        for (Food f : foodList) {
            // 현재 음식 - 이전 음식 시간
            int curFood = f.times - eatenFoodTimes;
            // 남은 음식 * 먹는 시간이 가장 적은 음식
            long tmp = (long) curLength * curFood;

            // afterStopSec >= tmp(현재 먹을 음식까지의 걸린 총 시간)
            if(afterStopSec >= tmp) {
                afterStopSec -= tmp;
                // curFood : 현째 까지 먹은 음식 시간이 쌓인다.
                eatenFoodTimes += curFood;
            } else {
                // 현재 먹을 음식(남은 음식 중 가장 적게 걸리는 음식)을
                // 남은시간(afterStopSec) 동안 다 못 먹움
                // 앞으로 afterStopSec 초 후의 방송이 멈춤
                List<Food> subList = foodList.subList(curId, food_times.length);
                subList.sort(new CompIdx());
                answer = subList.get((int) (afterStopSec % curLength)).id;
                break;
            }

            // 다 먹은 음식 제외
            curLength--;
            // 현재 음식의 인덱스를 알기 위해서
            curId++;
        }

        return answer;
    }

    private class Food {
        public int times;
        public int id;

        public Food(int times, int id) {
            this.times = times;
            this.id = id;
        }
    }

    private class CompTimes implements Comparator<Food> {
        @Override
        public int compare(Food a, Food b) {
            return Integer.compare(a.times, b.times);
        }
    }

    private class CompIdx implements Comparator<Food> {
        @Override
        public int compare(Food a, Food b) {
            return Integer.compare(a.id, b.id);
        }
    }
}