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

import java.util.*;

class Solution {
    class food{
        int turn;
        int remainder;
        
        food(int turn, int remainder){
            this.turn = turn;
            this.remainder = remainder;
        }
    }
    public int solution(int[] food_times, long k) {
        int answer = 0;
        
        List<food> remainFood = new LinkedList<>();
        
        for(int i=0; i<food_times.length; i++){
            remainFood.add(new food(i+1,food_times[i]));
        }
        
        while(k!=0){
            while(remainFood.get(0).remainder==0){
                remainFood.remove(0);   
            }
            
            remainFood.get(0).remainder --;
            if(remainFood.get(0).remainder >0){
            remainFood.add(new food(remainFood.get(0).turn,remainFood.get(0).remainder));
            remainFood.remove(0);
            }else{
            remainFood.remove(0);
            }
            
            if(remainFood.isEmpty()){
                return -1;
            }
            
            k--;
        }
        
        answer = remainFood.get(0).turn;
        
        return answer;
    }
}

정확성 테스트는 통과하였으나 효율성 테스트를 통과하지 못했다.

우선 ArrayList는 탐색에 효과적이고 LinkedList는 삽입과 삭제에 효과적이라는 사실을 이 문제를 풀다가 알게되었다.

0초부터 k초까지의 리스트의 순서를 바꿔가며 k초 이후의 순서를 알아냄.

>> 결과적으로 k가 매우 클때는 시간초과를 일으킴 

>> k를 1씩 줄이는 것이 아니라 크게크게 줄여갈 수 있는 방법을 생각해 봐야겠다.

 

import java.util.*;

class Solution {
    class food{
        int turn;
        int remainder;
        
        food(int turn, int remainder){
            this.turn = turn;
            this.remainder = remainder;
        }
    }
    
    public int solution(int[] food_times, long k) {
        
        int n=food_times.length;
        int flag = 0;
        int i=0;
        
        List<food> remainFood = new LinkedList<>();
        
        for(int j=0; j<n; j++){
            remainFood.add(new food(j+1,food_times[j]));
        }
        
        Collections.sort(remainFood, new Comparator<food>(){
           public int compare(food f1, food f2){
               return f1.remainder - f2.remainder;
           } 
        });
        
        for(food f : remainFood){
            long depth = f.remainder - flag;
            
            if(depth!=0){
                long spend = depth * n;
                if(spend <=k){
                    k -=spend;
                    flag = f.remainder;
                }else{
                    k %= n;
                    remainFood = remainFood.subList(i,food_times.length);
                    Collections.sort(remainFood,new Comparator<food>(){
                       public int compare(food f1, food f2){
                           return f1.turn - f2.turn;
                       } 
                    });
                    return remainFood.get((int)k).turn;
                }
            }
            ++i;
            --n;
        }
        
        return -1;
    }
}

remainder를 정렬하여  k를 한번에 많이씩 줄여나가는 방법으로 하니 통과하였다.