[프로그래머스] 호텔 대실 - Python3

프로그래머스의 레벨 2 문제 호텔 대실

문제 요구 조건 이해하기

필요한 최소 객실의 수를 알아내야 한다.

내 풀이 방법

1. 빈 방이 있으면 주고, 없으면 객실을 하나 늘린다.
2. 빈 방이 있는지 검사하는 방법은 예약 시작 시간과 방들의 퇴실 시간 + 10분을 비교한다.
3. 예약 목록을 예약 시작 시간을 기준으로 정렬하고 예약 목록을 순회하면서 1번을 반복한다.

 class Room:
     
     def __init__(self, t):
         self.time = t
         
     def change(self, t):
         self.time = t
         
     def is_empty(self, t):
         if self.time + 10 <= t:
             return True
         return False
         
 class Hotel:
     
     def __init__(self):
         self.rooms = []
 ​
     def add_room(self, t):
         self.rooms.append(Room(t))
     
     def book_room(self, start_t, end_t):
         for room in self.rooms:
             if room.is_empty(start_t):
                 room.change(end_t)
                 return True
         return False
 ​
 def solution(book_time):
     book_time.sort(key=lambda x:x[0])
     hotel = Hotel()
     
     for book in book_time:
         start_h, start_m, end_h, end_m = map(int, ':'.join(book).split(':'))
 ​
         if not hotel.book_room(start_h * 60 + start_m, end_h * 60 + end_m):
             hotel.add_room(end_h * 60 + end_m)
     
     return len(hotel.rooms)
             

풀이 회고

1. 문제 조건 중에 다음 손님은 퇴실 시간 + 10분부터 받을 수 있다는 것을 뒤늦게 확인했다. 문제 확인을 꼼꼼히 하고 기억하거나 적어두자. 분명 읽었는데 깜박했다.. ㅠㅠ
2. 이 방법은 예약의 최대가 1000개라서 풀 수 있었다. 예약의 수가 많아지면 이 방법은 O(n^2)이기 때문에 풀 수 없다.

다른 사람의 코드 공부

ChatGPT가 참고할만한 답을 하지 못했다. 테스트케이스에서 계속 틀린다! 그래서 프로그래머스의 다른 사람들의 코드를 공부하고 배운 점만 기록한다.

1. 시간을 1분 단위 배열로 저장해서 각 시간대에 사용 중인 방의 수를 누적합으로 나타냈다. 시작 시간에 +1, 끝나는 시간에 -1을 해두면 누적합으로 시작 시간과 끝나는 시간을 증가시킬 수 있다.
2. 누적합 배열 중에서 가장 큰 원소가 최소 객실의 수다.

누적합을 이용하면 O(n)으로 예약의 수가 많아져도 해결할 수 있다. 나는 왜 누적합을 생각하지 못했을까? 일단 단순한 방법으로 해결할 수 있는 범위의 문제이기 때문에 빠르게 생각난 방법으로 해결했다. 바로 누적합인걸 알려면 겹치는 부분과 그 부분의 원소의 값이 한 번에 사용 중인 객실의 수인 걸로 바꿔서 생각해야 했다. 그래도 풀긴 했으니까, 연습하다 보면 늘겠지!