목표

1. 사용자가 원하는 시간대에 열람실을 빠르게 검색할 수 있어야 함

• 해시테이블 & 이진 탐색 트리가 적절
  • 해시테이블-빠른 검색 시간
    • 데이터를 키-값 쌍으로 저장, 해시 함수로 키가 직접 주소로 매핑되어 바로 접근할 수 있으므로 빠르게 좌석 검색 가능
    • 시간 복잡도: O(1)
  • 이진 탐색 트리-정렬된 데이터에서 효율적 검색
    • 삽입과 삭제가 빈번함에도 순서대로 정렬하므로, 삽입과 삭제가 빈번함에도 원하는 시간대의 좌석을 빠르게 찾을 수 있음
    • 시간 복잡도: O(log n)

2. 시간 순서에 따라 정렬된 상태에서 삽입과 삭제가 빈번하게 이루어질 수 있어야 함

• 시간 순 관리는 연결리스트&큐, 예약취소 관리는 스택이 적절
  • 연결리스트-빠른 삽입과 삭제
    • 데이터가 연속적으로 배치되지 않고 포인터로 연결되므로, 중간에 신규 예약이나 취소가 발생해도 처리가 매우 빠름
    • 시간 복잡도: O(1)
  • 큐-선입선출, 시간 순 관리
    • 데이터를 시간 순으로 처리하므로 예약이 끝난 좌석을 자동으로 처리하고 정리하는 데 효율적
    • 시간 복잡도: O(1)
  • 스택-후입선출
    • 마지막으로 들어온 순서대로 취소할 수 있으므로, 좌석을 잘못 선택한 사용자의 실수 방지 가능
    • 시간 복잡도: O(1)

결론(자료구조 선택)

• 해시테이블 + 큐를 복합적으로 활용
  • 해시테이블-예약된 좌석 빠르게 확인 및 검색 가능
  • 큐-예약 시간이 끝난 좌석을 시간 순으로 자동 정리

시스템 구조 흐름도

https://boardmix.com/app/share/CAE.CMy5eiABKhDjSeZWikhmifrnNdO1tGZzMAZAAQ/kzd8sJ

파이썬 코드

import time

# 해시테이블 클래스 구현
class HashTable:
    def __init__(self):
        self.table = {}
    
    def insert(self, key, value):
        self.table[key] = value
    
    def get(self, key):
        return self.table.get(key, None)
    
    def update(self, key, value):
        if key in self.table:
            self.table[key] = value
        else:
            print(f"Key {key} not found.")
    
    def remove(self, key):
        if key in self.table:
            del self.table[key]
        else:
            print(f"Key {key} not found.")

    def display(self):
        for key, value in self.table.items():
            print(f"Seat {key}: {value[0]} - Time Slot: {value[1]}")

    def find_empty_seats(self):
        empty_seats = []
        for key, value in self.table.items():
            if value[0] == "notReserved":
                empty_seats.append(key)
        return empty_seats

# 큐 클래스 구현
class Queue:
    def __init__(self):
        self.queue = []
    
    def enqueue(self, item):
        self.queue.append(item)
    
    def dequeue(self):
        if len(self.queue) > 0:
            return self.queue.pop(0)
        else:
            print("Queue is empty.")
    
    def remove(self, item):
        for i, queued_item in enumerate(self.queue):
            if queued_item == item:
                self.queue.pop(i)
                return
    
    def display(self):
        for item in self.queue:
            print(f"Seat {item[0]} - Time Slot: {item[1]}")

# 예약 취소 관리 클래스
class AutoCancel:
    def __init__(self, seat_table, reservation_queue):
        self.seat_table = seat_table
        self.reservation_queue = reservation_queue
    
    # 예약 시간 검증 후 자동 취소 기능
    def auto_cancel_reservations(self):
        current_time = self.get_current_time()
        for seat_id, value in list(self.seat_table.table.items()):
            if value[0] == "reserved":
                reserved_time = value[1]
                if self.is_past_time(current_time, reserved_time):
                    self.cancel_reservation(seat_id)
    
    # 현재 시간을 구하는 함수 (예시로 "17:00" 형식으로 반환)
    def get_current_time(self):
        return "17:00"
    
    # 시간이 지났는지 확인하는 함수
    def is_past_time(self, current_time, reserved_time):
        return current_time >= reserved_time

    # 자동으로 예약을 취소하는 함수
    def cancel_reservation(self, seat_id):
        print(f"자동 취소: 좌석 {seat_id} 예약이 취소되었습니다.")
        self.seat_table.update(seat_id, ("notReserved", ""))
        self.reservation_queue.remove((seat_id, self.seat_table.get(seat_id)[1]))

# 메인 함수
def main():
    seat_table = HashTable()  # 해시테이블 객체
    reservation_queue = Queue()  # 큐 객체
    auto_cancel = AutoCancel(seat_table, reservation_queue)  # 자동 취소 객체

    # 초기 좌석 설정: 1부터 10까지의 좌석 존재
    for seat_id in range(1, 11):
        seat_table.insert(seat_id, ("notReserved", ""))

    while True:
        print("\\n=== 도서관 좌석 예약 시스템 ===")
        print("1. 예약")
        print("2. 취소")
        print("3. 자동 예약 취소")
        print("4. 종료")
        choice = input("원하는 메뉴를 선택하세요: ")

        if choice == "1":
            reserve_seat(seat_table, reservation_queue)
        elif choice == "2":
            cancel_reservation(seat_table, reservation_queue)
        elif choice == "3":
            # 자동 예약 취소 실행
            auto_cancel.auto_cancel_reservations()
        elif choice == "4":
            print("시스템을 종료합니다.")
            break
        else:
            print("잘못된 입력입니다. 다시 선택해주세요.")

# 예약 함수
def reserve_seat(seat_table, reservation_queue):
    print("\\n=== 예약 ===")

    # 빈 좌석 검색
    empty_seats = seat_table.find_empty_seats()
    if empty_seats:
        print(f"현재 빈 좌석 번호: {', '.join(map(str, empty_seats))}")
    else:
        print("빈 좌석이 없습니다.")
        return

    # 사용자로부터 예약할 좌석 번호 받기
    seat_id = input("예약할 좌석 번호를 입력하세요 (1~10): ")

    # 유효한 좌석 번호인지 확인
    if not seat_id.isdigit() or not 1 <= int(seat_id) <= 10:
        print("잘못된 좌석 번호입니다. 1부터 10까지의 번호를 입력해주세요.")
        return
    
    seat_id = int(seat_id)

    # 선택된 좌석이 예약 가능한지 확인
    if seat_table.get(seat_id) is not None and seat_table.get(seat_id)[0] == "reserved":
        print(f"좌석 {seat_id}는 이미 예약되었습니다. 다른 좌석을 선택해주세요.")
        return

    # 예약 시간대 입력 받기
    time_slot = input("예약할 시간대 (예: 17:00)를 입력하세요: ")

    # 예약 가능한 좌석이면 예약 실행
    seat_table.insert(seat_id, ("reserved", time_slot))
    reservation_queue.enqueue((seat_id, time_slot))
    print(f"좌석 {seat_id} 예약이 완료되었습니다. 예약 시간대: {time_slot}")

# 예약 취소 함수
def cancel_reservation(seat_table, reservation_queue):
    print("\\n=== 예약 취소 ===")
    
    # 사용자로부터 취소할 좌석 선택 받기
    seat_id = input("취소할 좌석 번호를 입력하세요 (1~10): ")

    # 유효한 좌석 번호인지 확인
    if not seat_id.isdigit() or not 1 <= int(seat_id) <= 10:
        print("잘못된 좌석 번호입니다. 1부터 10까지의 번호를 입력해주세요.")
        return

    seat_id = int(seat_id)

    # 예약된 좌석인지 확인
    if seat_table.get(seat_id) is None or seat_table.get(seat_id)[0] != "reserved":
        print(f"좌석 {seat_id}는 예약되지 않은 좌석입니다. 취소할 수 없습니다.")
        return

    # 예약 취소 처리
    seat_table.update(seat_id, ("notReserved", ""))
    
    # 큐에서 정확한 항목 제거
    reservation_queue.remove((seat_id, seat_table.get(seat_id)[1]))

    print(f"좌석 {seat_id} 예약이 취소되었습니다.")

# 주피터에서 실행할 때 main() 함수 호출
if __name__ == "__main__":
    main()

1. 시간 관리 위해 패키지 import

1. 해시테이블 구현