99클럽 코테 스터디 38일차 TIL + Heap(Seat Reservation Manager)

오늘의 과제

리트코드 medium으로 분류된 Seat Reservation Manager 입니다.

 

이번 유형은 힙 입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

좌석 예약 프로그램을 디자인합니다. 초기화 함수, 예약, 예약 취소 함수를 구현하면 되는데 예약시에는 가장 낮은 번호의 좌석 번호 순서대로 숫자를 반환합니다.

 

자료구조로서 힙은 최소 힙 혹은 최대 힙을 사용할텐데 문제의 요건을 보면 "가장 낮은 번호 순서대로" 좌석을 예약한다라고 나와있으니 최소 힙으로 사용하도록 하겠습니다. 이전 문제에서 사용했던 우선순위 큐를 사용할텐데 초기화시 정렬 순서에 따라 정렬된 값을 반환해주는 특성을 이용하겠습니다.

 

먼저 초기화입니다. 우선순위 큐를 선언 후 n만큼 예약이 가능하니 좌석을 예약 가능한 상태로 넣어줍니다. 이후에 값을 꺼낼때 마다 큐 안에 있는 값 중 가장 낮은 숫자부터 꺼내게됩니다.

PriorityQueue<Integer> pq;

public SeatManager(int n) {
    pq = new PriorityQueue<>();
    for (int i = 1; i <= n; i++) {
        pq.add(i);
    }
}

 

 

예약입니다. 예약 가능한 자리 중(큐에 있는 값 중) 가장 낮은 자리를 반환해야 합니다. 저희는 우선순위 큐를 사용하기 때문에 단순히 poll 만 해주면 됩니다.

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

 

예약 취소입니다. 해당 좌석을 사용 가능한 상태로 둬야 하기 때문에 다시 큐에 넣어줍니다. 어떤 번호의 좌석이 취소되더라도 다음 예약시엔 가장 낮은 좌석을 반환하게 됩니다.

public void unreserve(int seatNumber) {
    pq.add(seatNumber);
}

 

 

코드입니다.

class SeatManager {

    PriorityQueue<Integer> pq;

    public SeatManager(int n) {
        pq = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            pq.add(i);
        }
    }
    
    public int reserve() {
        return pq.poll();
    }
    
    public void unreserve(int 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);
 */

 

배운 점

이번 문제 기간에 우선순위 큐는 이용하여 문제를 풀었던 것 같은데 힙이라고 문제 분류가 나온 건 처음이라 조금 헷갈렸습니다. 덕분에 다시 힙이라는 자료 구조에 대해 찾아볼 수 있게 된 계기가 되었습니다. 항해 99가 끝나면 1일차부터 문제를 복기하며 각 자료구조에 대해 정리 + 구현을 정리해두고 문제 중간 중간에 참조 링크를 걸어두면 시간이 지나 다시 보던, 제가 풀었던 문제에 대한 도움을 얻고자 방문하신 누군가에게 도움이 되지 않을까 싶습니다.

 

 

오늘의 한줄평

반복 숙달만큼 단순하고도 효율적인 방법은 없다