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

완전탐색으로 하는 것이 아닌

먹는 시간이 짧은 순으로 음식을 1개씩 빼는 방식으로 문제를 해결함

음식을 빼다가 문제에서 주어진 k순을 넘어가는 경우를 체크해주어

넘어가기 전의 인덱스를 활용하여 k번째가 어떤 음식인지 찾아야함

Food 클래스를 선언하여 음식을 먹는데 걸리는 시간과 음식 번호를 표시해줌

Food 리스트를 선언해 주어진 food_times에 맞춰서 매칭해줌

Compator를 2개 써야하는데

1개는 시간에 대한 오름차순, 1개는 인덱스에 대한 오름차순을 위해 선언함

시간에 대한 오름차순으로 sorting 해주고

앞서 말한 음식 1개씩 빼는 방식으로 for문돌리다가

문제에서 요구하는 k번째 넘게 도달했을 때 따로 이벤트 처리해준 후

앞서 선언한 foods 배열에서 해당하는 index값을 return해준다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

import java.util.*; class Solution { class Food{ int time; int idx; Food(int t, int i){ time = t; idx = i; } } public int solution(int[] food_times, long k) { int answer = 0; List<Food> foods = new LinkedList<Food>(); int n = food_times.length; // 남아 있는 음식 수 for (int i = 0; i < n; i++) { foods.add(new Food(food_times[i],i+1)); } Comparator<Food> CompTime = new Comparator<Food>() { @Override public int compare(Food a, Food b) { // TODO Auto-generated method stub return a.time-b.time; } }; Comparator<Food> CompIdx = new Comparator<Food>() { @Override public int compare(Food a, Food b) { // TODO Auto-generated method stub return a.idx-b.idx; } }; foods.sort(CompTime); int pretime = 0; int i = 0; for (Food f : foods) { long diff = f.time - pretime; if(diff!=0) { long spend = diff * n ; if(spend <= k) { k-=spend; pretime = f.time; } else { k%=n; foods.subList(i, food_times.length).sort(CompIdx); return foods.get(i+(int)k).idx; } } i++; n--; } return -1; } }

참고 : https://www.youtube.com/watch?v=4MWxAt4fx5I&index=4&list=PL6YHvWRMtz7CyRH31LhCHR0gp_x7eeSK6