2 X 10^13
이고, food_times의 길이는 최대 200,000
, food_times의 각 원소는 최대 1,000,000,000
이므로 일반 배열을 순회하면서 풀었을 때 최악의 경우 200,000 x 2 x 10^13
의 시간 복잡도를 가진다e.g.
음식의 남은 시간과 음식의 번호를 담을 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;
}
}
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));
pq.peek().time
에서 직전 음식을 다 먹은 시간을 빼고 남은 음식의 개수를 곱해준다 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;
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