99클럽 코테 스터디 13일차 TIL + LeetCode 1845. Seat Reservation Manager

 

 

 

오늘은 사무실에서 카카오톡 알림톡 기능을 구현 성공하고 기분이 너무 좋아서 가벼운 발걸음으로 왔다~!

그리고 노트북 열어서 알고리즘 공부 스타트🔥

 

 

오늘 문제는 읽으면서 코드짤 때 뭐야 이게 끝이야? 싶었지만 역시나 숨겨진 문제가 있었다.

 

 

 

일단 문제를 읽어보니

SeatManager로 n값에 따라서 앉을 수 있는 자리 initialize,

reserve() 메소드로는 자리를 예약했으르로 가장 숫자가 작은 자리를 pop,

unreserve() 메소드로는 주어진 seatNumber에 따라서 다시 이 자리를 반납하도록 구현하면 된다.

 

그래서 코드도 그냥 그대로 쉽게 구현했다.

 

class SeatManager:


    def __init__(self, n: int):
    	self.seat = []
    	for i in range(n):
    		self.seat.append(i+1)

    def reserve(self) -> int:
    	self.seat.sort()
    	n = self.seat.pop(0)
    	return n

    def unreserve(self, seatNumber: int) -> None:
    	self.seat.append(seatNumber)

 

 

그리고 제출하면...!!!!

 

 

띠로리... 이렇게 시간 초과가 발생한다.

도대체 뭐가 문제일까 고민해봤을때 시간복잡도에 걸릴만한건 sort() 뿐이였다.

 

흠... 뭘 써야 정렬하면서 추가 혹은 정렬하고 pop이 가능할까?

=> heap을 사용해보자

 

💡 python에서 heap을 사용하기 위해서는 import heapq 후 사용할 수 있다. 

- heap push
  heapq.heappush(arr, x) : x라는 값을 arr에 push 및 min heap으로 heapify까지 완료 => O(logN)

- heap pop
   heapq.heappop(arr) : arr에서 min 값 pop 및 min heap 으로 heapify까지 완료 => O(logN)

- heapify
   heapq.heapify(arr) : arr을 min heap으로 heapify 진행 => O(NlogN)

 

 

기존에 내가 짠 코드가 왜 시간 초과가 나는가에 대해서 생각해봤다.

 

시나리오1. sort() 후 pop() 하기

 

💡 python 에서 sort() 함수는 Timsort를 사용하며 O(NlogN)의 시간복잡도를 가진다.

sort() -> O(NlogN) + pop(0) -> O(N) 로 수행하면 O(NlogN)이 된다.
(pop(0)은 맨 앞의 값을 pop하고 한칸씩 움직이는 연산이 필요)

 

 

시나리오2. heappop() 사용하기

 

💡 python에서 heappop()의 경우 O(logN)의 시간복잡도를 가진다.

따라서 heappop()을 이용해서 pop과 동시에 바로 min heap을 생성하도록 하면 sort연산을 없앨 수 있다는 장점이 있다.
heappop()으로 추출하면 O(logN)

 

 

따라서 heap을 활용하여 다시 코드를 작성했다.

 

import heapq

class SeatManager:

    def __init__(self, n: int):
        self.seat = []
        for i in range(n):
            self.seat.append(i+1)

    def reserve(self) -> int:
        n = heapq.heappop(self.seat)
        return n

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.seat,seatNumber)

 

이후 submit을 하면...!!!

 

 

시간초과 문제없이 잘 통과하는 것을 볼 수 있다!!

오늘도 하루 숙제 끄읕!!!!