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

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

프로그래머스

728x90

---

메모리: 86.8 MB, 시간: 108.45 ms

사용 알고리즘: 구현

 

우선 남은 음식들을 PriorityQueue(pq)에 담아두고 섭취하는데 가장 짧은 시간이 걸리는 음식을 꺼내 쓸 수 있게 해 준다.

현재 남은 음식 중, 섭취하는데 가장 짧은 시간이 걸리는 음식의 섭취 시간을 min이라고 했을 때

적어도 min 바퀴 돌 동안 남은 음식들은 모두 섭취 가능한 상태라고 보장할 수 있다. (min * pq.size())

따라서 k -= min * pq.size()는 한 번에 구해줄 수 있으므로 O(min * food_times.length) -> O(1)만큼 시간을 줄일 수 있다.

import java.util.*;

class Solution {
    public int solution(int[] food_times, long k) {
        
        // food_times를 올림차순으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < food_times.length; i++) {
            pq.add(food_times[i]);
        }
        
        // 몇 번 회전했는지 저장
        int count = 0;
        
        int min;
        while(!pq.isEmpty() && k >= pq.size()) {
            // 현재 가장 적게 남은 음식
            min = pq.peek() - count;
            
            // 가장 적게 남은 음식이 끝날 때까지 회전
            if(k >= (long)min * pq.size()) { // 타입 주의
                count += min;
                k -= (long)min * pq.size(); // 타입 주의
            }
            // 가장 적게 남은 음식이 끝날 때까지 회전하진 못한다면
            else {
                // 돌 수 있는 만큼은 돌기
                count += k / pq.size();
                k %= (long)pq.size(); // 타입 주의
            }
            
            // 끝난 음식 제거
            while(!pq.isEmpty() && pq.peek() == count) pq.poll();
        }
        
        // 회전할 수 있는만큼 회전했으므로
        // 마지막으로 순회하며 먹기 시작하는 음식 구하기
        int answer = -1;
        for(int i = 0; i < food_times.length; i++) {
            if(food_times[i] > count) k--;
            // 다시 먹기 시작하는 음식 찾음
            if(k == -1) {
                answer = i + 1;
                break;
            }
        }
        
        return answer;
    }
}