카카오 기출 무지의 먹방 라이브

효율성은 둘째치고 왜 답이 안맞지..

import java.io.*;
import java.util.*;

class FoodPlate implements Comparable<FoodPlate>{
    int index;
    int time;

    FoodPlate(int index, int time){
        this.index=index;
        this.time=time;
    }

    public int getTime() {
        return time;
    }
    public int getIndex(){
        return index;
    }

    @Override
    public int compareTo(FoodPlate foodPlate) {
        int time = foodPlate.getTime();
        if(this.time>time) return 1;
        else if(this.time==time) return 0;
        else return -1;
    }
}

class IndexComparator implements Comparator<FoodPlate>{
    @Override
    public int compare(FoodPlate f1, FoodPlate f2){
        return f1.getIndex() - f2.getIndex();
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        List empty = new ArrayList<Integer>();
        List foodList = new ArrayList<FoodPlate>();

        long totalFoodTime=0;

        for(int i=0;i<food_times.length;i++){
            totalFoodTime+=food_times[i];
        }

        if(totalFoodTime<=k){
            return -1;
        } //남은 음식 없음

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

        if(k<=food_times.length){
            return (int) (k-food_times.length+1);
        }

        foodList.sort(Comparator.naturalOrder());

        FoodPlate foodPlate;

        long litleTime;

        for(int i=0;i<food_times.length;i++){
            foodPlate= (FoodPlate) foodList.get(i);
            if(k/(food_times.length-empty.size())>=foodPlate.getTime()){
                litleTime=foodPlate.getTime();
                k-=litleTime*(food_times.length-empty.size());

                for(int j=i;j<food_times.length;j++){
                    foodPlate=(FoodPlate)foodList.get(j);
                    foodPlate.time-=litleTime;
                    if(foodPlate.time==0&&!empty.contains(j)){
                        empty.add(j);
                    }
                }
                if(foodPlate.time==0&&!empty.contains(i)){
                    empty.add(i);
                }
            }
            else{
                break;
            }
        }

        while (k>(food_times.length-empty.size())){
            litleTime=(k/(food_times.length-empty.size()));
            k-=litleTime*(food_times.length-empty.size());
            for(int j=empty.size();j<food_times.length;j++){
                foodPlate=(FoodPlate)foodList.get(j);
                foodPlate.time-=litleTime;
            }
        }

        Collections.sort(foodList,new IndexComparator());

        for(int i=0;k>=0&&i<food_times.length;i++){
            foodPlate=(FoodPlate)foodList.get(i);
            if(foodPlate.getTime()==0){
                continue;
            }
            k--;
            answer=i;

        }
        return answer+1;
    }
}

위 코드는 접근방식은 사실 영상이랑 비슷했습니다.

list에 있는 가장 작은 time부터 k에서 제거한다는 아이디어는 비슷했습니다.

그러나 효율성에서 문제가 발생했던 부분은

for(int i=0;i<food_times.length;i++){
            foodPlate= (FoodPlate) foodList.get(i);
            if(k/(food_times.length-empty.size())>=foodPlate.getTime()){
                litleTime=foodPlate.getTime();
                k-=litleTime*(food_times.length-empty.size());

                for(int j=i;j<food_times.length;j++){
                    foodPlate=(FoodPlate)foodList.get(j);
                    foodPlate.time-=litleTime;
                    if(foodPlate.time==0&&!empty.contains(j)){
                        empty.add(j);
                    }
                }
                if(foodPlate.time==0&&!empty.contains(i)){
                    empty.add(i);
                }
            }
            else{
                break;
            }
        }

이부분에서 실제로 list에서 값을 빼는 과정을 거쳤기 때문에 문제가 발생했습니다..

생각해보면 어차피 지금 나의 food_time-이전 food_time을 넘을수 없다는 사실을 간과 했습니다.

그래서 풀이 영상을 보고 푼 결과는 다음과 같습니다.

import java.io.*;
import java.util.*;

class FoodPlate implements Comparable<FoodPlate>{
    int index;
    int time;

    FoodPlate(int index, int time){
        this.index=index;
        this.time=time;
    }

    public int getTime() {
        return time;
    }
    public int getIndex(){
        return index;
    }

    @Override
    public int compareTo(FoodPlate foodPlate) {
        int time = foodPlate.getTime();
        if(this.time>time) return 1;
        else if(this.time==time) return 0;
        else return -1;
    }
}

class IndexComparator implements Comparator<FoodPlate>{
    @Override
    public int compare(FoodPlate f1, FoodPlate f2){
        return f1.getIndex() - f2.getIndex();
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        int answer = 0;
        List<FoodPlate> foodList = new ArrayList<FoodPlate>();

        long totalFoodTime=0;

        int n = food_times.length;

        for(int i=0;i<n;i++){
            totalFoodTime+=food_times[i];
        }

        if(totalFoodTime<=k){
            return -1;
        } //남은 음식 없음

        for(int i=0;i<n;i++){
            foodList.add(new FoodPlate(i+1,food_times[i]));
        }

        foodList.sort(Comparator.naturalOrder());

        long litleTime=0;
        long finish=0;
        long spend;
        int i=0;

        for(FoodPlate f : foodList){
            long diff = f.time - litleTime;
            if(diff!=0){
                spend = diff * n;
                if(k>=spend){
                    k-=spend;
                    litleTime=f.time;
                }else{
                    k %= n;
                    Collections.sort(foodList.subList(i,food_times.length),new IndexComparator());
                    return foodList.get(i+(int)k).index;
                }
            }
                n--;
                i++;

        }

        return -1;
    }
}

참조한 영상은 아래와 같습니다.
https://www.youtube.com/watch?v=4MWxAt4fx5I&t=125s
https://programmers.co.kr/learn/courses/30/lessons/42891