[코테] 99클럽 코테 스터디 38일차 TIL - 힙

Question1 - [미들러] 좌석 예약 매니저 (Seat Reservation Manager)

 

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

• SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
• int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
• void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

Example 1:

Input

["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]

[[5], [], [], [2], [], [], [], [], [5]]

Output

[null, 1, 2, null, 2, 3, 4, 5, null]

 

Explanation

• SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
• seatManager.reserve();    // All seats are available, so return the lowest numbered seat, which is 1.
• seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
• seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
• seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
• seatManager.reserve();    // The available seats are [3,4,5], so return the lowest of them, which is 3.
• seatManager.reserve();    // The available seats are [4,5], so return the lowest of them, which is 4.
• seatManager.reserve();    // The only available seat is seat 5, so return 5.
• seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

Constraints:

• 1 <= n <= 105
• 1 <= seatNumber <= n
• For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
• For each call to unreserve, it is guaranteed that seatNumber will be reserved.
• At most 105 calls in total will be made to reserve and unreserve.

---

 

문제풀이

 

heap의 성질을 이용해서, seat을 예약 및 취소하는 seat manager 클래스를 만드는 문제다. 

heap의 성질에 관해서는 아래 기본문제에 대한 포스팅을 참고 

https://ysryuu.tistory.com/71

[코테] 99클럽 코테 스터디 5일차 TIL - 힙

 

heapq는 기본적으로 '최소힙' 기능으로,

리스트를 힙으로 만들면 최소값부터 자동으로 오름차순 정렬이 되고, pop을 할때도 최소값부터 반환된다.

import heapq

# 리스트를 힙으로 변환
lst = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(lst)

print(lst)  # 출력: [1, 1, 2, 3, 5, 9, 4, 6]

print(heapq.heappop(lst))  # 출력: 1

 

 

힙 기능을 참고해서 문제를 풀어보자. 

원래 주어진 클래스 및 메소드 틀은 아래와 같다.

• init 메소드 : SeatManager 객체를 초기화 한다. 관리할 n개의 좌석을 생성 및 사용 가능 상태로 만든다.
• reserve 메소드 : 가장 번호가 작은 사용 가능한 좌석을 예약하고, 그 좌석 번호를 반환한다.
• unreserve 메소드 : 주어진 좌석 번호를 다시 사용 가능 상태로 되돌린다.

class SeatManager(object):

    def __init__(self, n):
        

    def reserve(self): # 비예약 자리중 최소값 자리 예약후 반환


    def unreserve(self, seatNumber): # 해당 숫자를 unreserved로

 

기능별로 작성된 풀이 코드는 아래와 같다. 

• heapq를 import 한다
• init 메소드에서, 리스트로 관리할 좌석을 seat객체로 만든다. 좌석 번호는 1~n까지.
• init 메소드에서, 좌석 리스트를 heap으로 만든다. heapq.heapify()를 해주면 리스트가 힙으로 바뀌고 자동정렬 된다.
• reserve 메소드에서, 항상 예약 가능한 좌석들 중 최소 수의 좌석을 예약 및 반환해야 하므로, return heappop()을 해주면 '가능한 좌석들 중 최소값'이 반환된다.
• 마지막으로 unreserve 메소드에서, seatNumber를 다시 가능한 좌석으로 만들어 주어야 하므로, heap에 해당 번호를 추가해서 반환하면 되므로 heapq.heappush()를 해주고 결과값을 반환한다.

import heapq

class SeatManager(object):

    def __init__(self, n): 
    	self.seats = [i for i in range(1, n+1)]
        heapq.heapify(self.seats)
        
    def reserve(self): 
    	return heapq.heappop(self.seats)

    def unreserve(self, seatNumber): 
    	return heapq.heappush(self.seats, seatNumber)