1. SUBJECT : Seat Reservation Manager

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int x=-1;
    public SeatManager(int n) {
        for(int i=1 ; i<=n; i++){
            pq.add(i);
        }    
    }
    
    public int reserve() {
        x = pq.poll();
        return x;
    }
    
    public void unreserve(int seatNumber) {
        pq.add(seatNumber);
    }
}

  PriorityQueue<Integer> pQ = new PriorityQueue<>();
    int n;
    int idx = 1;

    public SeatManager(int n) {
        this.n = n;
    }
    
    public int reserve() {
        if (pQ.size() > 0)
            return pQ.poll();
        return idx++;
    }
    
    public void unreserve(int seatNumber) {
        pQ.add(seatNumber);

두 코드는 시간 차이가 난다. 첫번째 코드는 88ms 두 번째는 33ms 정도 차이가 난다.

우선 둘은 모두 똑같은 로직을 가지고 있지만 초기화 pq를 초기화 하는 방법이 다르다.

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

pq에 값을 집어넣는 방식이다. 이때 pq는 정렬을 수행하게 되는데 이는 NlogN방식을 사용하게 된다.

즉!

초기화 작업을 수행할 때 시간을 많이 소요하게 된다는 것이다!!

  int n;
    int idx = 1;

    public SeatManager(int n) {
        this.n = n;
    }

어짜피 출력의 값은 오름차순으로 수행되므로 이와 같이 설정해준다. 만약에 출력의 값이 공차가 불규칙한 오름차순이면 위의 로직처럼 해야하지만 이처럼 공차를 가지는 경우에는 위처럼 설정하고

    public int reserve() {
        if (pQ.size() > 0)
            return pQ.poll();
        return idx++;
    }
    
    public void unreserve(int seatNumber) {
        pQ.add(seatNumber);
    }

reserve()에서 값을 리턴하고 ++연산자를 통해서 값을 추가해준다.

unreserve는 말 그대로 시트를 반환하는 것으로 그대로 pq에 넣어주면 된다.

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