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

[문제 출처]

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

1. 문제

설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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

2. 설명

함수부터 설명하자면 split 함수는 : 를 기준으로 나누어 int로 변환해주는 함수입니다.

plus_ten함수는 끝나는 시간에 10분을 더한후의 시간입니다

 

 

 먼저 들어오는 시간순으로 정렬을 하기 위해 sort를 해주었습니다.

그후 book_time의 사이즈만큼 포문을 돌렸습니다. split을 이용해서 in_time과 out_time을 구해주었습니다.

 

만약 deq이 비어있다면 10분후의 끝나는시간을 deq에 넣어줍니다.

만약 deq의 맨앞값(최소값)이 현재 들어온 시간보다 크다면, 10분후의 끝나는시간을 deq에 넣어줍니다.

만약 deq의 맨앞값(최소값)이 현재 들어온 시간보다 작거나 같다면, deq의 맨앞값이 들어온시간보다 클때까지 deq을 pop해줍니다. 그 후 10분후의 끝나는시간을 deq에 넣어줍니다.

 위의 작업이 끝난후에는 sort를 해주어 deq의 front가 최소값이 되도록 해줍니다.

 또한 deq.size()를 통해 방의 최대개수를 갱신해줍니다.

 

 

이런 형식으로 코드를 구현하였습니다.

 

 

3. 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
#include <sstream>

using namespace std;

vector<int> split(string str){
    istringstream itr(str);
    string buffer;
    vector<int>ans;
    
     while(getline(itr,buffer,':'))
        ans.push_back(stoi(buffer));
    
    return ans;
}

int plus_ten(vector<int> time){
    int hour=time[0];
    int min=time[1];
    
    if(min+10>=60){
        min=min-60;
        hour+=1;
    }
    return hour*100+min+10;        
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    deque <int> deq;
    
    // 들어오는시간순 정렬
    sort(book_time.begin(), book_time.end());

    // 방계산
    vector<int>in;
    vector<int>out_time;
    int in_time;
    int max_room=0;
    
    for(int i=0; i<book_time.size(); i++){
        in=split(book_time[i][0]);
        in_time=in[0]*100+in[1];
        out_time=split(book_time[i][1]);
        
        if(deq.empty()==1)
            deq.push_back(plus_ten(out_time));
        else if(deq.front()>in_time)
            deq.push_back(plus_ten(out_time));
        else if(deq.front()<=in_time){
            while(1){
                if(deq.front()>in_time || deq.empty()==1)
                    break;
                deq.pop_front();
            }
            deq.push_back(plus_ten(out_time));
        }
        sort(deq.begin(),deq.end());
        
        if(max_room<deq.size())
            max_room=deq.size();
    }
    
    return max_room;
}