[릿코드] Seat Reservation Manager

문제

릿코드 1845. Seat Reservation Manager

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

 

 

코드

import heapq

class SeatManager:
    def __init__(self, n):
        self.can_reserve = list(range(1, n + 1))
        heapq.heapify(self.can_reserve)    

    def reserve(self):
        return heapq.heappop(self.can_reserve)

    def unreserve(self, seatNumber):
        heapq.heappush(self.can_reserve, seatNumber)

 

 

풀이

def __init__(self, n):
    self.can_reserve = list(range(1, n + 1))
    heapq.heapify(self.can_reserve)

init 함수는 SeatManager의 객체를 초기화한다. 

n은 관리할 좌석의 수 이다.

self.can_reserve 는 예약 가능한 좌석을 나타내는 리스트 이다.

heapq.heapify()를 이용해서 self.can_reserve를 최소힙으로 바꾼다.

 

def reserve(self):
    return heapq.heappop(self.can_reserve)

reserve 함수는 예약 가능한 좌석 중에서 가장 작은 번호의 좌석을 예약한다.

self.can_reserve에서 가장 작은 값을 pop하고 반환한다.

이때 pop된 값은 예약된 좌석 번호이다.

 

def unreserve(self, seatNumber):
    heapq.heappush(self.can_reserve, seatNumber)

unreserve 함수는 주어진 좌석을 다시 예약한다.

heappush()의 매개변수로 받은 seatNumber를  self.can_reserve 힙에 추가한다.

 

 

새롭게 배운점 / 느낀점

• 파이썬 모듈은 heapq를 제공한다. 구조적으로는 min heap형태로 정렬된다. 내부적으로는 인덱스 0 부터 시작해서 k번째 원소는 항상 자식들(2k + 1, 2k + 2)보다 작거나 같다.
• heapq의 함수들
  • heapq.heappush(heap, item) : item을 heap에 추가한다.
  • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하고 pop된 값을 반환한다. 만약 heap이 비어있는 경우 인덱스에러가 난다.
  • heapq.heappify(lst) : 이미 생성해둔 lst 배열이 있다면, lst 배열을 min heap 형태로 바꾼다.

 

 

다른 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)