[Programmers] 호텔 대실(Lv.2)(C++)

풀이 소요시간 : 40분
시간 복잡도 : O(NlogN)

뭔가 금방 풀어야할 것 같은 문제였는데 나한테는 쉽지 않았다. 우선 시간 관련 문제가 나오는 경우 나는 stoi 등을 활용하여 int 형의 분 단위로 바꿔버리는게 속이 편한것같다.

각 호텔의 입실시간과 퇴실시간을 입실시간 기준으로 오름차순 정렬했다. 퇴실시간을 기준하여 정렬해도 크게 문제는 없을것 같긴한데, 일단 나는 우선순위 큐 를 활용하여 문제를 풀이했다.

이번차례에 다가온 예약 입실시간 이 아직 퇴실하지 않은 가장 빠른 퇴실시간 + 10분 보다 빠른경우 어쩔 수 없이 새로운 방을 입실하게 된다. 하지만 그렇지 않은 경우 최고 우선순위 방을 빼버리고 그 방에 투입한다. 이 과정은 우선순위 큐에서 pop 하고, 현재 예약을 우선순위 큐에 push 하는 과정이라고 할 수 있다.

정석 풀이과정을 찾아보려 한 결과, 다들 너무 가지각색 방식으로 풀었고 내 풀이도 나쁘지 않은것 같아 리팩토링을 따로 하지는 않았다.

전체 코드

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

priority_queue<int, vector<int>, greater<int>> PQ;


int solution(vector<vector<string>> book_time) {
    int N = book_time.size();
    sort(book_time.begin(), book_time.end());
    //시작 시간 순으로 오름차순 정렬
    
    int Cnt = 1;  
    PQ.push(stoi(book_time[0][1].substr(0, 2)) * 60 + stoi(book_time[0][1].substr(3)));
    
    
    for(int i = 1; i < N; i++)
    {
        int First = stoi(book_time[i][0].substr(0, 2)) * 60 + stoi(book_time[i][0].substr(3));
        int Last = stoi(book_time[i][1].substr(0, 2)) * 60 + stoi(book_time[i][1].substr(3));  
        
        if(PQ.top() + 10 <= First)
        {
            PQ.pop();
            PQ.push(Last);
        }
        else
        {
            Cnt++;
            PQ.push(Last);
        }
    }
    
    
    return Cnt;
    
    
}