1845. Seat Reservation Manager

문제

이번 문제는 문제 들어가기 전, 자료구조 힙에 대해 알아봐야 한다.

힙(heap) 이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중, 최대 값 혹은 최소 값을 빠르게 찾도록 만들어짐
• 반정렬 상태(느슨한 정렬 상태) 를 유지
  - 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말함
• 힙 트리에선 중복된 값 허용 (이진 탐색 트리에선 중복된 값을 허용 x)
• 삽입, 삭제 O(logn) 의 시간 복잡도 가짐

이 특성들을 가지고 코드를 구현해야 하며, PrioityQueue 변수를 선언해줘야 한다.

코드

class SeatManager {

    static PriorityQueue<Integer> PQ;
    public SeatManager(int n) {
        PQ = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) PQ.offer(i);
    }

    public int reserve() {
        return PQ.poll();
    }

    public void unreserve(int seatNumber) {
        PQ.offer(seatNumber);
    }
}

초반 초기화를 위해 new PriorityQueue<>() 를 사용하여 새로운 값을 삽입해준 후 입력받은 n 만큼 PQ 내에 삽입하면 된다.

reverse() 에선 순서대로 놓여져 있던(낮은 순부터) 예약자 손님을 반환하며 unreverse() 에선 예약했던 손님이 다시 예약 취소를 하여 PQ내 다시 삽입하게 되면, 우선순위 큐의 특성상 그 순서에 맞춰 정렬된다.