Daily Leetcoding Challenge 1845. Seat Reservation Manager

https://leetcode.com/problems/seat-reservation-manager

Seat Reservation Manager - LeetCode

오랜만의 포스팅이다. 그동안 리트코드를 전혀 안 하지는 않았다. 하지만 처음보다 텐션이 떨어지는 것은 틀림없다. 이것 외에도 할 것이 워낙 많아서 신경을 못쓰고 있다. 🥲 쉬운 문제라도 하루에 하나씩 풀자는 생각이었지만, 앞으로는 어려운 문제라도 조금씩 도전해보면서 기록해보려고 한다.

직관

SeatManager 클래스를 구현해야 한다. 1부터 n까지 n개의 자리가 있고, reserve() 함수를 호출하면 예약되지 않은 가장 작은 숫자를 리턴한다. 그리고 unreserve(int seatNumber)를 호출하면 인자로 받은 자리의 예약을 취소한다. 예약 시 좌석 번호가 1부터 순차적으로 증가하지만 예약을 취소하는 경우 빈자리 숫자가 더 이상 연속적이지 않다. 그래서 반환된 자리의 번호를 기록해둬야 한다.

순차적으로 증가한 좌석의 번호를 cur 변수에 저장해 둔다고 하자. 그러면 취소한 자리의 번호는 앞서 예약된 자리의 번호이기 때문에 항상 cur보다 작다. 그래서 반환된 자리를 모두 예약에 먼저 사용하고 난 뒤에 다시 cur부터 자리를 예약해야 한다.

접근법

cur는 순차적으로 증가하기 때문에 고민할 것이 없다.

반환된 자리를 관리할 방법만 생각해 보면 된다. ArrayList를 사용한다면 반환된 자리(숫자)를 넣고 정렬해 주는 작업을 반복해야 해서 효율적이지 않다. 최소힙을 사용하면 숫자를 넣을 때와 뺄 때 모두 O(logn) 시간에 처리할 수 있다.

복잡도

reserve() 메서드의 경우, worst case의 경우 우선순위큐(최소힙)에서 숫자를 꺼내야 하기 때문에 시간복잡도는 O(logn)이 된다. 그리고 unreserve() 메소드의 경우, 우선순위큐(최소힙)에 원소 1개를 넣는 작업이기 때문에 시간 복잡도는 O(logn)이다. reserve 또는 unreserve를 m번 호출하는 경우 전체 시간 복잡도는 O(mlogn)이 된다.

공간복잡도의 경우, 우선순위큐가 최대 n개의 원소를 저장할 수 있기 때문에 O(n)이다.

코드

class SeatManager {

    int size;
    int cur;
    Queue<Integer> pq = new PriorityQueue<>((a,b) -> a-b);

    public SeatManager(int n) {
        this.size = n;
        this.cur = 1;
    }
    
    public int reserve() {
        if (pq.isEmpty()) {
            return this.cur++;
        } else {
            return pq.poll();
        }
    }
    
    public void unreserve(int seatNumber) {
        pq.offer(seatNumber);
    }
}