프로그래머스 121689번
https://school.programmers.co.kr/learn/courses/15009/lessons/121689

문제

---

생각하기

---

• 정렬을 통해서 순서와 시간 관리를 하는 문제이다.

• PriorityQueue의 특성을 사용해야 한다.

동작

        for(int i=0; i<m; i++) {   
            int nowTime = i * k;

            // 나가는 손님이 먼저 퇴장한 다음 들어오는 손님이 입장한다.
            while(!pque.isEmpty() && pque.peek() <= nowTime) {
                pque.poll();
            }
            
            if(pque.isEmpty()) {
                // 가장 최근에 주문한 끝나는 시간
                lastOrderEndTime = nowTime + menu[order[i]];
            } else {
                lastOrderEndTime += menu[order[i]];
            }
            
            pque.offer(lastOrderEndTime);
            max = Math.max(max, pque.size());            
        }

문제에서 같은 시간에 나가는 사람과 입장하는 사람이 동시에 있을 경우 퇴장이 먼저 이루어진다고 했으므로 pque에서 poll()하는 작업을 우선하면 된다.

가장 마지막에 나갈 사람의 시간을 지속적으로 계산해서 다음 차례에 입장하는 사람이 언제 까지 대기해야 하는지 시간을 계산해서 pque에 넣으면 된다.

어차피 pque에서 가장 먼저나오는 값이 가장 먼저 나갈 사람이기 때문이다.

결과

코드

---

import java.util.*;

class Solution {    
    
    public int solution(int[] menu, int[] order, int k) {
        // 카페에서 최대 몇명이 머물렀는지 알고 싶다.
        int m = order.length;
        int max = 0;
        int lastOrderEndTime = 0;
        PriorityQueue<Integer> pque = new PriorityQueue<>();        
        
        for(int i=0; i<m; i++) {   
            int nowTime = i * k;

            // 나가는 손님이 먼저 퇴장한 다음 들어오는 손님이 입장한다.
            while(!pque.isEmpty() && pque.peek() <= nowTime) {
                pque.poll();
            }
            
            if(pque.isEmpty()) {
                // 가장 최근에 주문한 끝나는 시간
                lastOrderEndTime = nowTime + menu[order[i]];
            } else {
                lastOrderEndTime += menu[order[i]];
            }
            
            pque.offer(lastOrderEndTime);
            max = Math.max(max, pque.size());            
        }
        
        return max;
    } // End of solution()
} // End of Solution class