<Programmers> 무지의 먹방 라이브_Priority Queue java

문제 : 무지의 먹방 라이브

Idea

• 이 문제는 효율성 테스트를 따질 때, 방송시간(K) 값이 최대 2 X 10^13 이고, food_times의 길이는 최대 200,000, food_times의 각 원소는 최대 1,000,000,000 이므로 일반 배열을 순회하면서 풀었을 때 최악의 경우 200,000 x 2 x 10^13의 시간 복잡도를 가진다
• 각 음식의 시간을 오름차순으로 정렬하여, 시간이 가장 적게 걸리는 음식을 먹는다면 그 보다 더 오래 걸리는 음식도 시간이 적게 걸리는 음식만큼 먹게 될 것이다 라는 생각으로 접근한다

e.g.

Solution

1. class Food

• 음식의 남은 시간과 음식의 번호를 담을 class를 만든다

• 음식의 남은 시간 오름차순별로 sorting 하기 위해 Comparable을 구현하고 compareTo을 Override함

  class Food implements Comparable<Food> {
      int time;
      int idx;
  
      Food(int time, int idx) {
          this.time = time;
          this.idx = idx;
      }
  
      public int compareTo(Food food) {
          return this.time - food.time;
      }
  }

2. Priority Queue

• 위에서 선언한 class Food를 큐에 담으면서 음식의 남은 시간이 오름차순으로 정렬되게 Priority Queue를 만든다

    PriorityQueue<Food> pq = new PriorityQueue<>();
    for (int i = 0; i < food_times.length; i++)
        pq.offer(new Food(food_times[i], i + 1));

3. K 줄여가기

• n번째 먹을 남은 음식의 양 pq.peek().time에서 직전 음식을 다 먹은 시간을 빼고 남은 음식의 개수를 곱해준다
• 이 값을 지금까지 먹기위해 사용한 시간에 더해주고 K값과 비교해서 K값보다 작을 때까지 반복한다

		while (sum + (pq.peek().time - prev) * remain_food <= k) {
			int now = pq.poll().time;
			sum += (now - prev) * remain_food;
			remain_food -= 1;
			prev = now;
		}

4. 남은 음식 중에 선택

• 남은 음식들을 다시 음식 번호를 기준으로 sorting
• 전체 시간 K에서 지금까지 먹기 위해 사용한 시간 sum을 빼주고 이를 남은 음식 개수 (remain_food)로 나눈 나머지가 답이다

		ArrayList<Food> list = new ArrayList<>();
		while (!pq.isEmpty())
			list.add(pq.poll());

		list.sort((i1, i2) -> i1.idx - i2.idx);

		return list.get((int) ((k - sum) % remain_food)).idx;

Source Code

package greedy;

import java.util.*;

class Food implements Comparable<Food> {
	int time;
	int idx;

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

	public int compareTo(Food food) {
		return this.time - food.time;
	}
}

public class 무지의먹방 라이브 {
	public int solution(int[] food_times, long k) {

		long sum = 0;
		for (int i = 0; i < food_times.length; i++)
			sum += food_times[i];

		if (sum <= k)
			return -1;

		PriorityQueue<Food> pq = new PriorityQueue<>();
		for (int i = 0; i < food_times.length; i++)
			pq.offer(new Food(food_times[i], i + 1));

		long remain_food = food_times.length; // 남은 음식
		long prev = 0; // 직전 음식을 다 먹은 시간
		sum = 0; // 지금까지 먹기 위해 사용한 시간

		while (sum + (pq.peek().time - prev) * remain_food <= k) {
			int now = pq.poll().time;
			sum += (now - prev) * remain_food;
			remain_food -= 1;
			prev = now;
		}

		ArrayList<Food> list = new ArrayList<>();
		while (!pq.isEmpty())
			list.add(pq.poll());

		list.sort((i1, i2) -> i1.idx - i2.idx);

		return list.get((int) ((k - sum) % remain_food)).idx;
	}
}

Reference
https://www.youtube.com/watch?v=zpz8SMzwiHM
https://jhhj424.tistory.com/34