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

문제

 

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

프로그래머스

 

 

문제풀이

 

백준의 회의실 배정, 강의실 배정과 비슷한 문제이다.

정렬 + 우선순위 큐를 이용하여 풀었다.

 

먼저 문제에서 주어진 시각은 string형 이므로 int형으로 바꿔 시각을 분으로 모두 바꾼다.

퇴실을 하면 해당 방은 10분간 청소 시간이 필요하므로 분으로 바꿀 때 퇴실 시각에만 10분씩 더해준다.

 

변환이 모두 끝났으면 정렬을 통해 시작 시각을 기준으로 오름차순 정렬을 한다.

그다음 현재 시각에 사용하고 있는 방을 우선순위 큐를 이용하여 나타낼 것이다.

퇴실 시각이 빠른 순으로 정렬해야 현재 시각에 해당 방을 이용할 수 있는지를 알 수 있으므로 우선순위 큐는 퇴실 시각이 빠른 순으로 오름차순 정렬한다.

 

정렬된 대실 시각들을 탐색하면서 현재 대실 시작 시각과 같거나 이전에 이미 퇴실한 방이 있다면 계속 pop을 한다.

그다음 현재 시각에 쓸 방을 우선순위 큐에 push 한다.

 

반복문을 계속 탐색하면서 answer을 answer와 우선순위 큐의 사이즈 중 큰 값으로 갱신한다.

 

코드

#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<string>> s_book_time) {
    int answer(0), hour(0), min(0);
    vector<vector<int>>book_time(s_book_time.size(), vector<int>(2, 0));

    for (int idx = 0; idx < s_book_time.size(); ++idx) {
        hour = stoi(s_book_time[idx][0].substr(0, 2));
        min = stoi(s_book_time[idx][0].substr(3, 2));
        book_time[idx][0] = hour * 60 + min;

        hour = stoi(s_book_time[idx][1].substr(0, 2));
        min = stoi(s_book_time[idx][1].substr(3, 2));
        book_time[idx][1] = hour * 60 + min + 10;
    }

    sort(book_time.begin(), book_time.end());

    priority_queue<int, vector<int>, greater<int>>room;
    for (int idx = 0; idx < book_time.size(); ++idx) {
        int start = book_time[idx][0];
        int end = book_time[idx][1];
        while (!room.empty() && room.top() <= start) {
            room.pop();
        }
        room.push(end);
        int room_size = room.size();
        answer = max(answer, room_size);
    }

    return answer;
}