호텔 대실

문제

호텔을 운영 중인 코니는 예약 손님들을 위해 객실을 제공하려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간의 청소 시간이 필요하며, 청소가 끝난 후에야 다음 손님이 입실할 수 있습니다. 예약 시간이 문자열 배열 book_time으로 주어질 때, 코니에게 필요한 최소 객실의 수를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 예약 시간 배열 book_time (길이 1 이상 1,000 이하). 각 원소는 ["HH:MM", "HH:MM"] 형태의 입실, 퇴실 시간입니다.
• 출력: 필요한 최소 객실의 수

링크: https://school.programmers.co.kr/learn/courses/30/lessons/155651

풀이: 정렬과 우선순위 큐(Min-Heap)를 활용한 스위핑

예약 시간을 입실 시간 기준으로 정렬한 뒤, 사용 중인 객실들의 '청소 완료 시간'을 우선순위 큐로 관리하여 필요한 객실의 최대 개수를 구하는 정석적인 풀이입니다.

• 시간 변환 (문자열 파싱): "HH:MM" 형태의 문자열을 계산하기 쉽게 분(minute) 단위의 정수로 변환하는 stoi 메서드를 구현했습니다. (시간 * 60 + 분)
• 오름차순 정렬: book_time 배열을 입실 시간을 기준으로 오름차순 정렬합니다. 입실 시간이 같다면 퇴실 시간을 기준으로 오름차순 정렬하여 시간의 흐름대로 예약 건을 확인할 수 있도록 합니다.
• 우선순위 큐 (사용 중인 객실 관리):
  • 우선순위 큐 pq는 **현재 사용 중인 객실들의 '청소 완료(퇴실 시간 + 10분) 시간'**을 오름차순(Min-Heap)으로 보관합니다. 가장 빨리 청소가 끝나는 객실이 항상 큐의 맨 앞(peek())에 위치하게 됩니다.
  • 새로운 예약 건을 확인할 때마다, 큐에 있는 객실 중 청소가 이미 끝난 객실(pq.peek() <= 현재 입실 시간)을 모두 찾아 큐에서 제거(poll())합니다.
  • 이후 현재 예약의 청소 완료 시간(퇴실 시간 + 10)을 큐에 추가(add)합니다.
• 최소 객실 수 갱신: 큐의 크기(pq.size())는 특정 시점에 동시에 사용되고 있는 객실의 수를 의미합니다. 반복문이 진행되는 동안 큐의 크기가 가장 커졌을 때의 값이 곧 호텔 운영에 필요한 '최소 객실 수'가 되므로, 이를 ans에 지속적으로 갱신합니다.

코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        // 1. 입실 시간을 기준으로 오름차순 정렬 (입실 시간이 같으면 퇴실 시간 기준)
        Arrays.sort(book_time, (bt1, bt2) -> {
            int s1 = stoi(bt1[0]);
            int s2 = stoi(bt2[0]);
            if (s1 == s2) return stoi(bt1[1]) - stoi(bt2[1]);
            
            return s1 - s2;
        });
        
        int ans = 0;
        // 청소가 끝나는 시간을 저장할 우선순위 큐 (오름차순)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (String[] bt : book_time) {
            // 2. 현재 입실 시간보다 이전에 청소가 끝난 객실이 있다면 큐에서 제거
            while(!pq.isEmpty() && pq.peek() <= stoi(bt[0])) {
                pq.poll();
            }
            
            // 3. 현재 손님의 퇴실 시간 + 청소 시간(10분)을 큐에 추가
            pq.add(stoi(bt[1]) + 10);
            
            // 4. 동시 사용 객실의 최댓값 갱신
            ans = Math.max(ans, pq.size());
        }
        
        return ans;
    }
    
    // "HH:MM" 포맷을 분(minute) 단위 정수로 변환하는 헬퍼 메서드
    int stoi(String s) {
        return Integer.parseInt(s.substring(0, 2)) * 60 + Integer.parseInt(s.substring(3));
    }
}

알고리즘 분류

정렬 (Sorting), 우선순위 큐 (Priority Queue), 라인 스위핑 (Line Sweeping)