프로그래머스 - 호텔 대실

문제

프로그래머스 — 호텔 대실

접근 방법

모든 예약을 수용하는 데 필요한 최소 객실 수를 구한다. 한 회의실에서 최대한 많은 회의를 선택하는 회의실 배정 문제와는 목적이 다르다.

시각을 분 단위 숫자로 변환하고, 예약을 시작 시각의 오름차순으로 처리한다. 각 객실에는 다음 손님을 받을 수 있는 시각인 퇴실 시각 + 10분을 저장한다.

현재 예약의 시작 시각 이하에 청소가 끝나는 객실이 있으면 그 객실을 재사용한다. 없다면 객실을 추가한다. 재사용 가능한 객실 중 어느 것을 선택해도 된다. 이 시점에 모두 사용 중이라면 현재 예약까지 동시에 수용할 새 객실이 반드시 필요하기 때문이다.

객실별 상태를 별도 배열에 저장하면 입력 예약을 변경하지 않고 방의 재사용 조건을 직접 표현할 수 있다.

코드

function solution(book_time) {
  const toMinutes = (time) => {
    const [hour, minute] = time.split(':').map(Number)
    return hour * 60 + minute
  }
  const bookings = book_time
    .map(([start, end]) => [toMinutes(start), toMinutes(end) + 10])
    .sort((a, b) => a[0] - b[0])
  const readyTimes = []

  for (const [start, readyAt] of bookings) {
    const room = readyTimes.findIndex((time) => time <= start)
    if (room === -1) {
      readyTimes.push(readyAt)
    } else {
      readyTimes[room] = readyAt
    }
  }

  return readyTimes.length
}

복잡도와 경계 조건

예약 수가 n이면 정렬은 O(n log n), 객실 탐색은 최악의 경우 O(n²)이다. 추가 공간은 O(n)이다. 예약이 최대 1,000개인 조건에서 단순 배열 탐색을 사용했다. 더 큰 입력에서는 청소 완료 시각을 관리하는 최소 힙을 고려할 수 있다.

청소가 끝나는 시각과 다음 입실 시각이 같으면 재사용할 수 있다. 23:59 퇴실 후의 청소 완료 시각도 분 단위 숫자로 유지하며, 자정으로 되돌리지 않는다.