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

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

프로그래머스

 

문제 유형 : 큐 , 구현

문제 난이도 : Level 2

 

문제 설명

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

 

풀이

문자열의 시간들을 정수로 변환시켜서, 시작 시간을 기준으로 정렬한다.

큐에 시작 시간, 종료 시간 페어들을 삽입한다.

퇴실 시간들을 담는 배열 rooms를 만든다.(rooms의 크기 = 방의 개수)

 

큐에 데이터가 있는동안, 큐를 하나씩 뽑아서

그 값의 시작 시간이 현재 있는 rooms들의 퇴실 시간에다가 10을 더한 값보다 큰지 확인하고, 더 크면 그 방의 퇴실 시간을 이번 예약의 퇴실 시간으로 바꾼다.

지금 있는 방을 다 돌고 나서도 찾은 게 없다면, rooms의 맨 뒤에 지금의 퇴실 시간을 넣는다.(방 하나 더 생성)

 

큐를 다 빼고나면, rooms의 크기는 최소 방의 개수가 된다.

 

코드

C++

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

using namespace std;

int solution(vector<vector<string>> book_time) {
    vector<pair<int, int>> bookings;
    for(const auto& time : book_time) {
        int startTime = stoi(time[0].substr(0, 2)) * 60 + stoi(time[0].substr(3, 2));
        int endTime = stoi(time[1].substr(0, 2)) * 60 + stoi(time[1].substr(3, 2));
        bookings.push_back(make_pair(startTime, endTime));
    }
    
    sort(bookings.begin(), bookings.end(), [](const auto& a, const auto& b) {
        return a.first < b.first;
    });

    queue<pair<int, int>> q;

    for(const auto& time : bookings) {
        q.push(time);
    }

    vector<int> rooms;
    while(!q.empty()) {
        int curr_start = q.front().first;
        int curr_end = q.front().second;
        q.pop();
        bool booked = false;
        for(int i = 0; i < rooms.size(); i++) {
            if(curr_start >= rooms[i] + 10) {
                rooms[i] = curr_end;
                booked = true;
                break;
            }
        }
        if(!booked) {
            rooms.push_back(curr_end);
        }
    }
    
    return rooms.size();
}