2019 - 무지의 먹방 라이브

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

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

[ 문제풀이 ]

K 초동안 모든 음식을 순서대로 탐색한다면 정확성은 해결할 수 있지만 K가 최대 2 x 10^13이기 때문에 효율성은 통과할 수 없다. 그렇다면 어떻게 해야 효율성을 통과할 수 있을까?

​나는 보통 효율성 문제 같은 경우 제일 먼저 정렬을 해보는 편이다. K = 7, food_times가 [3, 1, 2, 2, 5]일 경우 food_times이 낮은 순으로 정렬해보자.

이전의 매초마다 food_times를 하나씩 없애는 방법을 조금 더 빨리 처리할 수는 없을까? 현재 가장 낮은 food_times는 1이다. 오름차순으로 정렬되어 있기 때문에 뒤의 food_times들은 최소 1 이상이라는 것이 보장된다.

​즉, 현재 남아있는 모든 food_times의 개수 x 가장 낮은 food_times 값이 K보다 작거나 같으면 일일이 하나씩 처리할 필요 없이 한 번에 처리할 수 있다.

그렇다면 현재 남아있는 모든 food_times의 개수 x 가장 낮은 food_times 값이 K보다 크다면 어떻게 해야 할까? 현재 4 x 2 = 8은 2보다 크기 때문에 이전의 방법으로는 한 번에 처리할 수 없다.

​사실 단순하게 남은 food_times들 중 K 번째 인덱스를 가지는 food_times를 찾아주면 된다. 하지만 이 과정에서의 K가 상황에 따라 굉장히 클 수 있기 때문에 K 번째 인덱스의 food_times을 순차적으로 찾는 것은 결국 처음 방법과 다를 게 없는 방법이다.

따라서 한 번에 처리한 방법처럼 K를 남은 food_times의 개수만큼 mod 연산을 해준다면 K 번째 인덱스를 빠르게 구할 수 있다.

​또한, 우리가 처음에 food_times을 기준으로 정렬한 상태이기 때문에 남은 food_times를 다시 idx 기준으로 정렬해 줘야 한다.

import java.util.*;

class Solution {
    class Food implements Comparable<Food> {
        int idx, time;
        
        Food (int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
        
        public int compareTo(Food o) {
            return this.time - o.time;
        }
    }
    
    public int solution(int[] food_times, long k) {
        List<Food> foods = new ArrayList<>();
        for (int i = 0; i < food_times.length; ++i) {
            foods.add(new Food(i + 1, food_times[i]));
        }
        
        //food를 time을 기준으로 정렬
        Collections.sort(foods);
        
        int before = 0; //이미 처리한 time
        for (int i = 0; i < foods.size(); ++i) {
            //효율성을 위해 i번째부터 끝까지의 food에서 일괄 처리
            //total이 int를 벗어날 수 있기 때문에 long으로
            long time = foods.get(i).time - before;
            long total = time * (foods.size() - i);
            
            if (k >= total) {
                k -= total;
                before += time; //처리한 time 누적
            } else {
                //i번째 food부터 끝까지 idx를 기준으로 정렬
                foods.subList(i, food_times.length).sort((o1, o2) -> o1.idx - o2.idx);
                
                //효율성을 위해 k를 남은 food의 개수만큼 나눠줌
                k %= (foods.size() - i);
                
                return foods.get((int)k + i).idx;
            }
        }
        return -1;
    }
}