99클럽 코테 스터디 28일차 TIL - 힙

오늘의 학습 키워드

힙
우선순위 큐

---

알고리즘 문제

• LeetCode Medium. 1845. Seat Reservation Manager

---

공부한 내용

PriorityQueue

---

오늘의 회고

처음 시도

• 처음엔 "데이터를 추가하고 꺼내야 한다." 는 생각으로 stack, queue를 생각하다가 "숫자가 작은 순서대로 꺼내야 한다." 조건에서 priorityQueue로 풀어야겠다고 생각했다. 

해결

• 자료구조를 바로 생각해내고, 15분 이내로 풀어서 성공적인 느낌!
• 입력 값인 n만큼 큐에 좌석(숫자)를 넣어놓고, 예약하면 큐에서 꺼내고 예약 취소 시 매개변수인 좌석 번호를 다시 큐에 넣는다.

---

문제 풀이

import java.util.*;

class SeatManager {
    private PriorityQueue<Integer> queue;
    public SeatManager(int n) {
        this.queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i+1);
        }
    }
    
    public int reserve() {
        return queue.poll();
    }
    
    public void unreserve(int seatNumber) {
        queue.offer(seatNumber);
    }