프로그래머스: 호텔 예약

알고리즘 문제 해결 과정을 기록합니다

November 21, 2025 · 3 min read

문제 개요 #

Source: 프로그래머스 - 호텔 대실 (155651)
Difficulty: Level 2
Key Concept: Greedy, Priority Queue, Sweeping

호텔 예약 시간이 담긴 배열이 주어질 때, 예약 시간이 겹치지 않게 모든 손님을 받기 위해 필요한 최소 객실 수를 구해야 합니다.. (단, 퇴실 후 10분간 청소 시간이 있어야 다음 손님을 객실에 받을 수 있음)

접근 방법 #

가장 빨리 비워지는 방을 찾는 것이 핵심입니다. 그러기 위해서 시간 단위를 통일하고, 예약 시간을 기준으로 방을 정렬부터 먼저 하였습니다.

시간 단위 통일
- 현재 시간은 HH:mm 형태의 문자열
- 이를 모두 분으로 환산하여 시간 표현
정렬
- 먼저 온 손님부터 방을 배정해야 함
- 입실 시간을 기준으로 예약 시간들을 정렬

정렬과 시간 단위 통일이 모두 이루어졌다면 방 배정 전략을 세워야 합니다. 기존의 사용중인 객실 중 가장 빨리 청소가 마무리되는 객실의 시간을 찾아 다음 입실 시간보다 빠르다면 방이 재사용 가능합니다. 그렇지 못하다면 새로운 객실을 할당해주어야 합니다.

시행착오 #

처음 문제에서 제한 사항을 확인하였습니다.

제한 사항: $ 1 \le \text{book\_time의 길이} \le 1000 $

따라서 $N=1000$이므로 1초내에 $O(N^2)$도 가능하다고 생각하여 완전 탐색으로 구현해도 충분할것이라 생각했습니다. 물론 이 방법으로도 해당 문제를 통과할 수는 있었습니다. 하지만 다른 분들의 문제 풀이를 보고 해당 문제는 priority_queue를 통해서 풀었을 때 이상적으로 최적화됨을 확인하였습니다. 이에 다시 priority_queue를 통해 해당 문제를 다시 풀어 $N=1,000,000$인 경우에도 풀 수 있도록 코드를 재작성 하였습니다.

해결 방법 #

#include <bits/stdc++.h>
using namespace std;

// 시간("HH:MM")을 분(Minute) 단위 정수로 변환하는 헬퍼 함수
int getTimes(string time){
    return stoi(time.substr(0,2)) * 60 + stoi(time.substr(3,2));
}

int solution(vector<vector<string>> book_time) {
    // Min-Heap: 종료 시간이 가장 빠른 방이 top에 오도록 설정
    // C++ priority_queue는 기본이 Max-Heap이므로 greater<int> 사용
    priority_queue<int, vector<int>, greater<int>> pq;

    // 1. 입실 시간 기준 오름차순 정렬
    sort(book_time.begin(), book_time.end());

    for(auto& times: book_time){
        int start = getTimes(times.front());
        int end = getTimes(times.back()) + 10; // 청소 시간 10분 포함

        // 2. 가장 빨리 비는 방(pq.top())이 있고, 재사용 가능하다면?
        // (가장 빨리 끝나는 시간 <= 현재 내 입실 시간)
        if(!pq.empty() && pq.top() <= start){
            pq.pop(); // 기존 방의 종료 시간 제거 (이어서 쓰므로)
        }

        // 3. 현재 예약의 종료 시간을 큐에 등록
        // (새 방을 쓰든, 이어서 쓰든 종료 시간은 갱신됨)
        pq.emplace(end);
    }

    // 4. 큐에 남아있는 요소 수 = 동시에 필요했던 최대 방의 개수
    return pq.size();
}

알고리즘 설명 #

sort: $O(N\log N)$, 모든 예약 입실 시간 순서대로 정렬, 이를 통해 현재 처리 중인 예약 이후 예약들은 모두 무조건 입실 시간이 늦거나 같게됨
Min-heap: $O(\log N)$, 우선순위 큐에는 각 방의 청소 종료 시간만 저장
Sweeping: 예약을 하나씩 꺼내면서 힙의 top과 비교($O(N)$)

$\text{top} \le \text{start}$ : 해당 방을 이어서 사용 가능하므로 pop
$\text{top} > \text{start}$ : 가장 빨리 비는 방도 청소가 끝나지 않음, 새로운 방을 할당해야 함(pop하지 않고 emplace)

heap의 크기가 필요한 방의 개수

성능 분석 #

Time Complexity: $O(N\log N)$
- 정렬에 $O(N\log N)$ 소요
- 루프를 N번 돌면서 pop, emplace를 수행하므로 $O(N\log N)$ 소요
Space Complexity: $O(N)$

실무 활용 #

Gemini를 통해 탐색하였습니다.

서버 리소스 오토스케일링: 특정 시간대에 물리는 트래픽 처리키위해 필요한 서버 인스턴스의 수 예측
CI/CD 파이프라인: 동시에 실행되는 빌드 작업들을 처리하기위해 몇 개의 워커 노드가 필요한지 계산

핵심 정리 #

이번 문제를 보면서 Priority Queue를 떠올려야 하는 몇 가지 조건들에 대해 학습하였습니다.

데이터가 동적으로 입출력이 있으면서, 최솟값 또는 최댓값을 지속적으로 조회하는 경우
가장 ~~한 상태인 것을 $O(1)$로 찾아야 할 때
$N$의 크기가 커 $O(N^2)$로는 되지 않을 때

유사문제 #

백준 11000번: 강의실 배정