99클럽 코테 스터디 38일자 TIL +seat-reservation-manager

문제 출처

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

학습 키워드

큐/스택 - 우선순위큐

시도 방법

우선순위큐는 내부적으로 값을 정렬하여 적재한다.
이 점을 활용하여 문제를 풀었다.

내가 작성한 코드

class SeatManager {
    
    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); 
    }
}

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

코드설명

우선순위큐는 데이터를 추가하면 자동으로 정렬상태를 보장한다.
만약 [1,2,5,6] 의 큐 상태에 3을 추가하면 [1,2,3,5,6] 이 되는 것이다.
문제에서 예약은 빠른 번호를 번호 출력한다고 했기 때문에 우선순위큐의 바로 앞 데이터를 제공(poll)하면 된다.
특정 좌석을 취소하면 큐에 적재를 하는데 이 경우에도 자동 정렬이 되므로 적재(offer)만 하면 된다.

출력결과

새롭게 알게된 점

없음

다음에 풀어볼 문제 - reduce-array-size-to-the-half

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL