[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT

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

 

📝 풀이 과정

단순 시뮬레이션으로 구현할 수도 있지만 그렇게 하면 효율성을 통과하지 못하기 때문에 아이디어가 필요하다.

5, 2, 10 => 2, 5, 10

2, 5, 10 => 0, 3, 8 => 0, 0, 5 

음식의 시간순으로 오름차순 정렬을 하고, 남은 시간을 크기 순으로 한 번에 제거하면 그만큼 시간을 줄일 수 있게 된다.

 

 

while (idx < foods.size()) {
  long min = foods.get(idx).time - prev;

  if (min * (foods.size() - idx) > k) break;
  k -= min * (foods.size() - idx);

  prev += min;
  idx++;
}

먼저, 시간 순으로 정렬한 음식의 List를 생성하고 idx를 하나씩 늘려가며 앞의 값과 현재 값의 차와 남은 음식 개수의 곱을 계산해 k에서 빼주었다. 만약 k의 값보다 계산 값이 크다면 남은 음식을 먹던 중 반환할 음식이 있는 경우기 때문에 반복문을 탈출한다.

 

어떤 음식을 반환해야하는지 계산하기 위해 idx - 1까지 음식은 모두 0이므로 subList()를 통해 잘라주었다. 다시 음식을 번호 순으로 재정렬하고, 만약 남은 음식이 하나도 없다면 foods.size()는 0이 되므로 -1을 반환하고 아니라면 k번째 먹게 되는 음식을 구한다.

 

💻 코드

import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
   public int solution(int[] food_times, long k) {
        List<Food> foods = IntStream.range(0, food_times.length)
                .mapToObj(i -> new Food(i + 1, food_times[i]))
                .sorted(Comparator.comparing(f -> f.time)).collect(Collectors.toList());

        long prev = 0;
        int idx = 0;
        while (idx < foods.size()) {
            long min = foods.get(idx).time - prev;

            if (min * (foods.size() - idx) > k) break;
            k -= min * (foods.size() - idx);

            prev += min;
            idx++;
        }

        foods = foods.subList(idx, foods.size()).stream()
                .sorted(Comparator.comparingInt(f -> f.idx))
                .collect(Collectors.toList());
        return foods.size() == 0 ? -1 : foods.get((int) (k % foods.size())).idx;
    }

    class Food {
        int idx, time;

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