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

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

 

시간 k의 범위가 위와 같으므로, 완전 탐색을 통하여는 효율성 테스트를 통과할 수 없음

 

다음과 같은 예시

food_times = {4, 5, 5, 5, 1, 3}
k = 15

 

이의 막대그래프를 그려보면 다음과 같다

x : index, y : cost

효율적인 계산을 수행해야하므로.. 얘를 cost ASC 순으로 재정렬해보면

 

 

cost ASC 순으로 정렬한 그래프

위처럼 정렬되는데.. 코드 상에서는 priority queue를 통하여 위처럼 정렬하였다

따라서 큐를 poll할 때마다 cost가 제일 낮은 음식 순서대로 pop되는 것

이렇게 pop한 푸드 정보값을 통하여 시간을 계산한다

 

 

 

 

시간을 계산할 때에는 푸드 정보를 통하여 계산해야 하므로 위와 같이 계산할 수 있다

즉 맨 처음 cost = 1, idx = 5인 푸드를 통하여 맨 밑의 사각형의 크기(시간)가 6이라는 것을 계산할 수 있다

 

 

대략적 순서

1. cost 순으로 푸드 데이터 정렬

2. 정렬된 푸드 정보를 통해 시간 묶음 단위(위에서의 사각형)로 소요 시간 계산

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
   static class Food implements Comparable<Food> {
      int idx;
      long time;

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

      //time asc, idx asc
      @Override
      public int compareTo(Food o) {
         if (this.time == o.time) {
            return this.idx - o.idx;
         }
         return (int)(this.time - o.time);
      }
   }

   public int solution(int[] food_times, long k) {
      //init
      PriorityQueue<Food> foods = new PriorityQueue<>();
      long totalTime = 0;
      for (int i = 0; i < food_times.length; i++) {
         Food food = new Food(i + 1, food_times[i]);
         foods.add(food);

         totalTime += food_times[i];
      }

      long currTime = 0;
      long height = 0;
      if (k < totalTime) {
         while ((foods.peek().time - height) * foods.size() <= (k - currTime)) {

            int length = foods.size();
            Food currFood = foods.poll();
            currTime += (currFood.time - height) * length;
            height = currFood.time;
         }

         int idx = (int)((k - currTime) % foods.size());
         ArrayList<Food> foodList = new ArrayList<>(foods);
         //"남은" 푸드 중에 idx번째의 푸드를 return
         Collections.sort(foodList, Comparator.comparingInt(o -> o.idx));
         return foodList.get(idx).idx;
      }
      return -1;
   }
}