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

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

 

문제설명

 

문제풀이 방법

1. 일단, Collection.sort를 사용해서 먹는 시간이 가장 빠른 순으로 정렬
2. while문을 통해 빠른시간 순서대로 값을 빼내서 그 크기만큼 곱해준다.
   1. 코드 : ( foods.get(0).time - cnt ) * n
   2. while문의 조건식을 보면, 남은 k번을 돌아가는 데 있어, foods의 size가 더이상 줄어들지 않는 크기를 찾아낼 수 있다. 
   3. 그렇게 하면 더이상의 작업을 할 필요없이 index를 구해주면된다.
3. Food 클래스의 num(index) 순서대로 정렬하고, ( k % n ) 를 통해 num의 값을 찾아주면 된다. 

 

내가 계속 틀렸던 이유

• ArrayList를 사용했다.
  • 사실, ArrayList를 사용한다고 문제가 발생하는 것은 아니다.
  • 나의 경우는, while문에서 arrayList의 index 0을 remove를 계속했다.
  • 이것이 문제가 되는 이유는, 0을 remove 하는 과정에서 배열들을 앞으로 땡겨줘야 하기 때문이다. ( 이렇게 되면 시간복잡도가 O(N * N) 이 된다. )

 

해결방법

• LinkedList를 사용하기
•  ArrayList의 정렬을 내림차순으로 한 후, index N-1번째 수를 제거하기

 

정확성만 고려한 코드

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

public class MujiEatingLive {
 
    public int solution(int[] food_times, long k) {

         ArrayList<food> arr = new ArrayList<>();

    long isEnough = 0;
        for(int i=0; i<food_times.length; i++) {
        arr.add(new food(i+1, food_times[i]));
        isEnough += food_times[i];
        }

        if(isEnough <= k) return -1;

        int index = 0;
        while(k>0) {
        	k--;
        	if(arr.get(index).size -1 == 0) {
        		arr.remove(index);
        		index = (index) % arr.size();
        	}else {
        		arr.get(index).size -= 1;
        		index = (index + 1) % arr.size();
        	}
        }

        return arr.get(index).num;
  	}
}

 

완성 소스 코드( 효율성 모두 고려)

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

public class MujiEatingLive {

    public static int solution(int[] food_times, long k) {

        LinkedList<Food> foods = new LinkedList<Food>();

        int n = food_times.length;
        long isEnough = 0;
        for(int i=0; i < n; i++) {
            foods.add(new Food(i+1, food_times[i]));

            if(isEnough <= k) isEnough += food_times[i];
        }
        if(isEnough <= k) return -1;

        Collections.sort(foods);

        long cnt = 0;

        while ( k > ( foods.get(0).time - cnt ) * n ) {
            k -= ( foods.get(0).time - cnt ) * n;
            cnt = foods.get(0).time;
            foods.remove(0);
            n--;
        }

        Collections.sort(foods, new Comparator<Food>() {
            @Override
            public int compare(Food o1, Food o2) {
                return o1.num - o2.num;
            }
        });

        return foods.get( (int) ( k % n ) ).num;
    }

    static class Food implements Comparable<Food>{
        int num;
        int time;

        Food(int num, int size) {
            this.num = num;
            this.time = size;
        }

        @Override
        public int compareTo(Food o) {
            return this.time - o.time;
        }
    }
}

 

 

문제링크

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

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