[프로그래머스]level.2 - 호텔 대실(C++)

문제

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

내 풀이

시작 시간을 기준으로 예약을 오름차순 정리한다.

방을 배정하면서 멀티셋에 다음 예약자가 들어올 수 있는 시간을 저장한다. ( 예약 종료 시간 + 10 )

셋을 사용하는 이유는 시간을 오름차순 정렬하여 다음 예약자가 최대한 빨리 들어올 수 있는 시간을 구하기 쉽게하기 위함이다. 그 중에서 멀티셋을 이용한 이유는 예약 시간이 중복될 수 있기 때문이다.

다음 예약자를 받을 때, 멀티셋에 저장된 배정 가능한 시간 중 예약자가 입실 가능한 시간이 있다면 멀티셋에서 해당 시간을 삭제하고 새 예약자에 맞춰 배정 가능한 시간을 갱신한다. 예약자가 입실 가능한 시간이 없다면 멀티셋에서 삭제할 거 없이 다음 예약자가 들어올 수 있는 시간을 추가하면 된다. 

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>

using namespace std;

// 시간 오름차순 정렬
bool comp(vector<string> t1, vector<string> t2)
{
    int hour_1 = stoi(t1[0].substr(0, 2));
    int hour_2 = stoi(t2[0].substr(0, 2));
    int min_1 = stoi(t1[0].substr(3));
    int min_2 = stoi(t2[0].substr(3));

    if(hour_1 != hour_2)
        return (hour_1 < hour_2);
    else    
        return (min_1 < min_2);
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    multiset<int> available_times; // 방 배정 가능 시간 저장
    
    // 시작 시간을 기준으로 예약을 정렬한다
    sort(book_time.begin(), book_time.end(), comp);
    
    for(const auto& b : book_time)
    {
        // 현재 예약의 체크인/체크아웃 시간
        int in_time = stoi(b[0].substr(0, 2)) * 60  + stoi(b[0].substr(3));
        int out_time = stoi(b[1].substr(0, 2)) * 60  + stoi(b[1].substr(3));
        
        // 배정 가능한 방이 있는지 체크한다
        auto iter = available_times.begin();
        for(; iter != available_times.end(); ++iter)
        {
            if(*iter <= in_time)
            {
                available_times.erase(iter); // 배정 가능한 방이 있다면 갱신을 위해 멀티셋에서 제거한다
                break;
            }
        }
    
        // 방 배정 가능 시간을 추가한다
        available_times.insert(out_time + 10);
    } 
    
    answer = available_times.size();
    
    return answer;
}