[프로그래머스][C++] 호텔 대실

호텔 대실

문제 링크

호텔 대실

분석

최소한의 객실 수로 손님을 모두 수용하고, 필요한 최소 객실의 수를 구하는 문제입니다.

입실 시각과 퇴실 시각이 주어지며, 퇴실 후에 청소 시간이 10분 있습니다.

모든 예약 시간을 분 단위로 변환하면 연산하기 간편합니다.

퇴실 시간에 청소 시간을 추가해줍니다.

모든 예약을 시작 시간 순으로 정렬해줍니다.

방이 현재 사용중이고, 사용할 수 있는 방이 없다면 새 방을 추가합니다.
만약 사용할 수 있는 방이 있다면 재사용합니다.

방들의 퇴실 시간은 최소 힙을 사용하여 관리할 수 있습니다.

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// HH:MM을 분으로 변환하는 함수
int timeToMinutes(const string& timeStr)
{
    int hour = stoi(timeStr.substr(0, 2)); // 시간
    int minute = stoi(timeStr.substr(3, 2)); // 분
    
    return hour * 60 + minute;
}

int solution(vector<vector<string>> book_time) {
    // 각 예약을 입실 시간과, 퇴실 시간 + 청소시간으로 변환하는 반복문
    vector<pair<int, int>> bookings;
    for (const auto& time : book_time)
    {
        int inTime = timeToMinutes(time[0]);
        int outTime = timeToMinutes(time[1]) + 10;
        
        bookings.push_back({inTime, outTime});
    }
    
    // 입실 시간을 기준으로 정렬
    sort(bookings.begin(), bookings.end());
    
    // 최소 힙
    // 현재 사용 중인 방들의 퇴실 시간을 저장
    priority_queue<int, vector<int>, greater<int>> pq;
    
    // 예약을 순회
    for (const auto& booking : bookings)
    {
        int inTime = booking.first; // 현재 예약의 입실 시간
        int outTime = booking.second; // 현재 예약의 퇴실 시간

        // 가장 빠른 퇴실 시간이 현재 입실 시간보다 작거나 같다면 제거
        if (!pq.empty() && pq.top() <= inTime)
        {
            pq.pop();
        }
        
        // 새로운 방 혹은 재사용된 방의 퇴실 시간을 추가
        // 즉, 입실 처리
        pq.push(outTime);
    }
    
    // 마지막에 남있는 방의 수가 필요한 최소 객실 수
    return pq.size();
}

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 각 예약을 입실 시간과, 퇴실 시간 + 청소시간으로 변환하는 반복문 $O(n)$
• 정렬 함수 $O(n \ log \ n)$
• 예약을 순회하는 반복문 $O(n)$
  • 힙 연산의 삽입과 삭제 $O(log \ k)$ 최대 $O(log \ n)$
    • k는 힙의 크기
  • 반복문과 과 힙 연산 $O(n \ log \ n)$
• $O(n) + O(n \ log \ n) + O(n \ log \ n)$

공간 복잡도는 $O(n)$입니다.

• 입실과 퇴실 시간을 저장하는 vector<pair<int, int>> bookings $O(n)$
• 현재 사용 중인 방들의 퇴실 시간을 저장하는 priority_queue<int, vector<int>, greater<int>> pq $O(n)$
• $O(n) + O(n)$

테스트 1 〉 통과 (0.02ms, 4.11MB)
테스트 2 〉 통과 (0.06ms, 4.21MB)
테스트 3 〉 통과 (0.26ms, 4.21MB)
테스트 4 〉 통과 (0.15ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.24ms, 3.91MB)
테스트 7 〉 통과 (0.23ms, 4.21MB)
테스트 8 〉 통과 (0.12ms, 3.69MB)
테스트 9 〉 통과 (0.07ms, 3.71MB)
테스트 10 〉 통과 (0.18ms, 4.14MB)
테스트 11 〉 통과 (0.29ms, 4.13MB)
테스트 12 〉 통과 (0.28ms, 4.14MB)
테스트 13 〉 통과 (0.06ms, 4.14MB)
테스트 14 〉 통과 (0.24ms, 4.2MB)
테스트 15 〉 통과 (0.37ms, 4.21MB)
테스트 16 〉 통과 (0.11ms, 4.14MB)
테스트 17 〉 통과 (0.30ms, 4.21MB)
테스트 18 〉 통과 (0.28ms, 4.14MB)
테스트 19 〉 통과 (0.23ms, 4.14MB)