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

https://school.programmers.co.kr/learn/courses/30/lessons/155651?language=cpp# 

프로그래머스

 

풀이

끝 시간 기준 우선순위 큐(최소 힙)를 사용해서 새로 예약하는 객실의 시작 시간과 현재 우선순위 큐의 top의 끝시간 +10분 과 비교한다. 끝시간+10분 보다 크다면 바로 들어갈 수 있으므로 우선순위 큐에서 기존의 객실을 빼준다. 그 다음 우선 객실과도 계속해서 비교해주고 pop 해주면 객실 수를 최소로 유지할 수 있다.

 

리뷰

첫 번째는 내가 짠 코드이고, 두 번째는 다른 분의 깔끔한 코드를 참고한 것이다. 시간을 string -> int 전환할 때 분 단위로 하지 않고 기존의 시:분 구조를 유지하다 보니 시간 체크부터 전반적인 코드가 많이 길어졌다.

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

using namespace std;

struct Time{
    int sh, sm;
    int eh, em;
    Time(vector<string>& a){
        sh = (a[0][0]-'0')*10+(a[0][1]-'0');
        sm = (a[0][3]-'0')*10+(a[0][4]-'0');
        eh = (a[1][0]-'0')*10+(a[1][1]-'0');
        em = (a[1][3]-'0')*10+(a[1][4]-'0');
    }
    bool check(Time& b){
        if (em+10 >= 60){
            return (eh+1)*100+(em+10-60) <= (b.sh*100+b.sm);
        }
        return (eh*100+em+10) <= (b.sh*100+b.sm);
    }
    
    bool operator<(const Time& a) const {
        return eh*100+em > a.eh*100+a.em;
    }
};

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    sort(book_time.begin(), book_time.end());
    vector<Time> v;
    for (int i=0; i<book_time.size(); i++){
        v.push_back(Time(book_time[i]));
    }
    priority_queue<Time> pq;
    pq.push(v[0]);
    answer++;
    for (int i=1; i<v.size(); i++){
        while (!pq.empty()){
            Time t = pq.top();
            if (t.check(v[i])){
                pq.pop();
            }
            else {
                break;
            }
        }
        pq.push(v[i]);
        if (answer < pq.size())
            answer = pq.size();
    }
    
    return answer;
}

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

using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    sort(book_time.begin(), book_time.end());
    
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i=0; i<book_time.size(); i++){
        string st = book_time[i][0];
        string et = book_time[i][1];
        int nst = stoi(st.substr(0,2))*60+stoi(st.substr(3));
        int net = stoi(et.substr(0,2))*60+stoi(et.substr(3));
        
        while (!pq.empty() && pq.top()+10 <= nst){
            pq.pop();
        }
        pq.push(net);
        answer = max(answer, (int) pq.size());
    }
    
    return answer;
}