Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 좌석 예약 관리자(Seat Reserve Manager) 구현하기

n개의 좌석에 대한 예약 상태를 관리하는 시스템을 설계해야 한다고 가정해 봅시다. 좌석은 1번부터 n번까지 번호가 매겨져 있으며, 우리는 다음과 같은 기능을 제공하는 SeatReserveManager 클래스를 구현해야 합니다.

  • 생성자(__init__) : n을 입력으로 받아 1부터 n까지 번호가 매겨진 n개의 좌석을 관리하는 객체를 초기화합니다. 초기 상태에서는 모든 좌석이 비어 있어 예약 가능합니다.
  • reserve() : 아직 예약되지 않은 좌석 중 가장 번호가 작은 좌석을 찾아 예약하고, 그 좌석 번호를 반환합니다.
  • unreserve(seatNumber) : 지정된 seatNumber에 해당하는 예약된 좌석 하나를 예약 취소합니다.

동작 예시

다음과 같은 입력이 주어졌다고 해보겠습니다.

  • obj = SeatReserveManager(7)
  • obj.reserve()
  • obj.reserve()
  • obj.reserve()
  • obj.unreserve(2)
  • obj.unreserve(5)
  • obj.reserve()
  • obj.reserve()

이 경우 출력은 1, 2, 3, 2, 5가 됩니다. 처음 세 번의 reserve() 호출로 좌석 1, 2, 3이 순차적으로 예약됩니다. 이후 2번과 5번 좌석을 예약 취소하지만, 5번 좌석은 아직 예약된 적이 없으므로 실제로는 2번만 해제됩니다. 따라서 이후 reserve() 호출 시 2번, 그리고 새로운 좌석인 5번이 차례대로 배정됩니다.

문제 해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

  • n을 인자로 받는 생성자(__init__)를 정의합니다.
  • current_seat := 0으로 초기화합니다. (마지막으로 배정된 좌석 번호 추적용)
  • empty_seats := 새로운 리스트로 초기화합니다. (예약 취소된 좌석 저장용)
  • reserve() 함수를 정의합니다.
    • empty_seats의 길이가 0보다 크면:
      • s := empty_seats의 최솟값
      • empty_seats에서 s를 제거
      • s를 반환
    • 그렇지 않으면 current_seat를 1 증가시킨 후 반환합니다.
  • unreserve() 함수를 정의합니다. seatNumber를 empty_seats의 끝에 추가합니다.

구현 코드

아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.

class SeatReserveManager:
   def __init__(self, n):
      self.current_seat = 0
      self.empty_seats = []

   def reserve(self):
      if len(self.empty_seats) > 0:
         s = min(self.empty_seats)
         self.empty_seats.remove(s)
         return s
      self.current_seat += 1

      return self.current_seat

   def unreserve(self, seatNumber):
      self.empty_seats.append(seatNumber)

obj = SeatReserveManager(7)
print(obj.reserve())
print(obj.reserve())
print(obj.reserve())
obj.unreserve(2)
obj.unreserve(5)
print(obj.reserve())
print(obj.reserve())

입력

obj = SeatReserveManager(7)
print(obj.reserve())
print(obj.reserve())
print(obj.reserve())
obj.unreserve(2)
obj.unreserve(5)
print(obj.reserve())
print(obj.reserve())

출력

1 2 3 2 5

복잡도 개선 팁

위 구현에서 min() 함수는 리스트 전체를 탐색하므로 O(n)의 시간이 걸립니다. 예약 취소된 좌석이 많아지면 성능이 저하될 수 있는데, 이 경우 heapq 모듈(최소 힙)을 사용하면 reserve() 연산을 O(log n)으로 최적화할 수 있습니다. heappush()로 좌석을 추가하고 heappop()으로 가장 작은 번호의 좌석을 꺼내면 됩니다. 또한 중복 좌석이 힙에 들어가지 않도록 집합(set)으로 관리하는 것도 좋은 방법입니다.