leetCode - 1845. Seat Reservation Manager java 풀이

 

class SeatManager {
    // 예약 / 해지
    // 낮은 순으로 예약 가능
    // 해지는 원하는 숫자에 가능

    // Set 이랑 PQ 쓰면 되지 않나?
    // 낮은 숫자로 만드는건 PQ
    // 예약 되었는지는 Set

    PriorityQueue<Integer> pq; // 여기 있는 것들은 남은 자리
    Set<Integer> set; // 여기 있는 것들은 이미 누군가 앉은 자리
    // 자리를 뺄 때에는 set 에 있는지 파악해서 있으면 set 에서 지우고 pq 에 넣어주면 된다.
    // pq 에 있는건 무조건 빈자리
        // 그럼 set 의 용도는? 뺄 수 있는지 확인을 위함
    int size;

    public SeatManager(int n) {
        this.size = n;
        pq = new PriorityQueue<>();
        for(int i=1; i<=n; i++) pq.add(i);
        set = new HashSet<>();
    }
    
    public int reserve() {
        // 처음 예약할 때
        if (set.size() < size) {
            // 남은 가장 작은 숫자를 가져와서
            int min = pq.remove();
            set.add(min);
            return min;
        } else {
            return -1;
        }
    }
    
    public void unreserve(int seatNumber) {
        if (set.contains(seatNumber)) {
            set.remove(seatNumber);
            pq.add(seatNumber);
        }
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

너무 간단하게 풀었는데 공간복잡도에서 이슈가 좀 있다.

다른 풀이를 생각해 보니 가장 작은 seat 하나를 두고 PQ 를 반대로 쓰면 좀 줄어들 수는 있어 보인다.