2025. 4. 8 알고리즘 코드카타

알고리즘 코드카타 - 115. 호텔 대실

문제 링크

문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
• book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
  [대실 시작 시각, 대실 종료 시각] 형태입니다.
• 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
• 예약 시각이 자정을 넘어가는 경우는 없습니다.
• 시작 시각은 항상 종료 시각보다 빠릅니다.

---

입출력 예

book_time	result
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

입출력 예 설명
입출력 예 #1

• 위 사진과 같습니다.

입출력 예 #2

• 첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.

입출력 예 #3

• 세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.

풀이 코드

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

using namespace std;

int convert(string input)
{
    int hour = stoi(input.substr(0,2));
    int minute = stoi(input.substr(3,2));
    int converted = (hour * 60) + minute;
    
    return converted;
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
    
    // 입실시간 빠른 순으로 정렬
    sort(book_time.begin(), book_time.end());
    
    // 정렬된 배열 순회
    for(auto& reserv : book_time)
    {
        int endtime = convert(reserv[1]);
        int starttime = convert(reserv[0]);
        int cleanroom = 10;
        
        // 퇴실이 가장 빠른 방이 다음 예약전에 퇴실한다면
        if(!pq.empty() && pq.top().first <= starttime)
        {
            pq.pop();
        }
        
        // 입실 처리
        pq.push({endtime + cleanroom, starttime});
        
        // 최대 방 수 갱신
        int rooms = pq.size();
        answer = max(answer, rooms);
    }
    
    return answer;
}

• 최소 힙 자료구조(Min Heap), 우선순위 큐를 이용한 풀이

• 문제에서 요구하는 것은 주어진 예약을 다 쳐냈을 때(=book_time 순회가 끝났을 때), 사용한 방의 개수.

• 큐의 선입선출 구조를 이용하기 위해 입실 순서대로 book_time을 정렬하고, 퇴실도 순서대로 이루어져야 하므로 priority_queue를 이용해야 한다.

  풀이 코드에서 주어진 배열을 정렬하지 않고 사용하면?

  예를 들어

  첫 번째 예약정보 (13:00~13:30)
  두 번째 예약정보 (10:00~11:00)

  위와 같은 입력이 있을 때, 정렬되지 않은 상태라면 두 번째 예약 정보의 입실 시각이 첫 번째 예약정보의 퇴실 시각 + 10 보다 작으므로 방을 하나 더 할당하게 되어 2개를 사용하게 된다.
  하지만 정렬하고 사용했다면? 방 1개로 해결.

• string으로 주어진 입퇴실 시각을 비교하기 위해 분으로 환산하는 함수가 필요하다.

• 나머지는 문제에서 요구하는 순서대로 코드를 작성하면 된다.

1. book_time을 순회한다 (= 입실 시각이 빠른 순으로 손님이 온다)
2. 현재 이용 중인 객실(pq.top())의 퇴실 시각 + 청소 시간이 손님의 입실 시각보다 빠르다면 해당 방을 재사용.
3. 그렇지 않다면 새로운 객실 할당.
4. 모든 손님이 입실했을 시점에 pq.size()의 최댓값이 가장 붐볐을 때의 방 사용 수가 되고 이것을 answer로 반환.