[프로그래머스] level4 42891 - 무지의 먹방 라이브(Java)

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

접근 방법

1. 큐를 사용하며 음식을 넣고 빼기를 반복한다.

그런데 k가 2*10^13이라 O(k)에선 적합하지 않다.

import java.util.*;

class Food{
    int index;
    int cal;

    public Food(int index, int cal) {
        this.index = index;
        this.cal = cal;
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        Queue<Food> queue = new LinkedList<>();
        for(int i=0;i<food_times.length;i++){
            queue.add(new Food(i+1, food_times[i]));
        }

        for(int i=0;i<k;i++){
            Food food = queue.poll();
            food.cal--;
            if(food.cal != 0){
                queue.add(food);
            }
        }
        
        if(queue.isEmpty()){
            return -1;
        }

        return queue.peek().index;
    }
}

2. 힙을 통해 시간이 적게 걸리는 음식부터 처리한다.

시간이 적은 음식을 먼저 해치우고 -> O(N)
음식의 개수를 줄이며 -> N 줄임
남은 음식을 마저 해치운다. -> O(NlogN)

소스 코드

import java.util.ArrayList;
import java.util.PriorityQueue;

class Food implements Comparable<Food> {
    int index;
    int cal;

    public Food(int index, int cal) {
        this.index = index;
        this.cal = cal;
    }

    @Override
    public int compareTo(Food o) {
        if (this.cal < o.cal) {
            return -1;
        }
        return 1;
    }
}

class Solution {
    public int solution(int[] food_times, long k) {
        long summary = 0;
        for (int i = 0; i < food_times.length; i++) {
            summary += food_times[i];
        }
        if (summary <= k) return -1;

        PriorityQueue<Food> heap = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            heap.add(new Food(i + 1, food_times[i]));
        }

        summary = 0; // 먹기 위해 사용한 시간
        long previous = 0; // 직전에 다 먹은 음식 시간
        long length = food_times.length; // 남은 음식의 개수

        // 이걸 다 돌면, 다 먹어치울 음식은 힙에서 제거된다.
        while (summary + (heap.peek().cal - previous) * length <= k) {
            int now = heap.poll().cal;
            summary += (now - previous) * length;
            length--;
            previous = now;
        }

        // 남은 음식은 인덱스 기준으로 정렬
        ArrayList<Food> result = new ArrayList<>(heap);
        result.sort((f1, f2) -> {
            if (f1.index < f2.index) {
                return -1;
            }
            return 1;
        });

        // 기존의 시간 k에 사용한 시간 summary를 빼서 나머지를 구함
        return result.get((int) ((k - summary) % length)).index;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{1, 2, 3}, 5));
    }
}