[99클럽 코테 스터디 38일차 TIL] 1845. Seat Reservation Manager

Seat Reservation Manager - LeetCode

 

• 1 <= n <= 10의 5제곱
• 1부터 10만까지.
• 1초의 시간 제한이 있다고 하고 1초에 실행할 수 있는 연산 횟수가 약 1억번이라고 할 때,  데이터의 개수(n)이 100,000이면 최대 시간복잡도가 O(nlogn)이 되도록 해야 한다.
• 힙 정렬, 퀵 정렬, 합병 정렬을 사용할 수 있다.

 

<내 풀이>

import heapq
class SeatManager:
    def __init__(self, n: int):
        self.h = []
        for i in range(1, n+1):
            self.h.append(i)
        self.res = []
        self.res.append('null')

    def reserve(self) -> int:
        a= heapq.heappop(self.h)
        self.res.append(a)
        return a
        
    def unreserve(self, seatNumber: int) -> None:
        b = heapq.heappush(self.h, seatNumber)
        self.res.append('null')

        


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

 

 

• heapq 모듈의 heapq.heappop, heapq.heappush를 이용했다.

 

• 세 개의 함수에서 모두 h, res 배열을 사용해야 함. 공통으로 클래스 인스턴스를 참조하기 위해서 self를 사용했다.
• self.h, self.h를 __init__ 함수에서 정의하고, 클래스 내의 메서드들에서 인스턴스 변수에 접근하거나 다른 메서드를 호출할 때 사용한다.