[C++] 호텔 대실 (프로그래머스 LEVEL 2)

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

프로그래머스

 

---

문제풀이

 

생각보다 많이 어려웠다. 처음 생각했던 방법은 "퇴실 시간"을 기준으로 오름차순 정렬하여 푸는 것이다.

1. 종료 시간을 큐에 넣어준다.

2. 큐의 맨 위에 있는 값 + 10 이 그 다음 값(현재 값)의 시작시간보다 작다면 큐의 값을 하나 빼주고 다시 큐의 값과 비교한다.

3. 만약 큐가 비거나, 위의 조건에 맞지않을 경우 큐에 현재 값을 넣어준다.

4. 큐의 사이즈가 최대가 될 경우가 정답이 된다.

라고 생각하였는데 이렇게 하면 문제가 있다.

[["05:57", "06:02"], ["04:00", "06:59"], ["03:56", "07:57"], ["06:12", "08:55"], ["07:09", "07:11"], ["04:00", "06:02"]]

위의 예시를 보자. 문제는 4번 값을 수행할 때 나온다. 4번값을 수행하면서 1, 2, 3번 값이 큐에서 빠지게 된다. 그 이후 5, 6번이 수행되며 결국 최댓값은 3이 나오게 된다. 그런데 그림을 보면 알수 있듯이, 1, 2, 3, 5번 4개가 겹치므로 답은 4이다.

 

두 번째 방법은 "시작 시간"을 기준으로 정렬해 위와 같은 방식으로 처리한 것이다.

이렇게 하면 시작 시간 순으로 값이 들어오므로 위에서 겪었던 문제를 피할 수 있다. 하지만 추가로 처리해 주어야 할 것이 있는데, 큐 값을 오름차순으로 정렬할 필요가 있다. 이를 위해 우선순위 큐를 사용했다.

오름차순으로 정렬해야 하는 이유는 겹치는 것중 가장 빨리 끝나는 시간과 다음 값을 비교해야 겹칠지 아닐지 알 수 있기 때문이다. 이해하기 어렵다면 한번 차근차근 다시 생각해보면 좋을것 같다.

 

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

using namespace std;

bool checkIn(string a, string b) {
    int a_hour = (a[0] - '0')*10 + a[1] - '0';
    int a_minute = (a[3] - '0')*10 + a[4] - '0';
    int b_hour = (b[0] - '0')*10 + b[1] - '0';
    int b_minute = (b[3] - '0')*10 + b[4] - '0';
    
    a_hour += (a_minute+10)/60;
    a_minute = (a_minute+10)%60;
    if(a_hour < b_hour) return true;
    if(a_hour == b_hour && a_minute <= b_minute) return true;
    return false;
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    sort(book_time.begin(), book_time.end(), cmp);
    priority_queue<string, vector<string>, greater<string>> q;
    
    for(int i=0; i<book_time.size(); i++) {
        while(!q.empty() && checkIn(q.top(), book_time[i][0])) q.pop();
        q.push(book_time[i][1]);
        answer = max(answer, (int)q.size());
    }
    return answer;
}

추가로, 처음 checkIn을 string& a, string& b와 같이 사용했는데 오류가 발생하였다. 원인은 pq를 사용하면서 q.top()으로 가져온 값이 string이 아닌 어떤 이상한 값이였기 때문이다.

라이브러리를 사용해 타입을 출력해 보면

NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE

라는 괴상한 데이터 타입이 나온다. 사실 뭔말인지 정확히 이해는 안된다... 여튼 주솟값 안쓰고 그냥 call by value로 불러주면 알아서 string으로 형변환이 되는 것 같다.

https://stackoverflow.com/questions/58912896/why-the-output-of-the-auto-variable-displays-something-not-related-to-type

why the output of the auto variable displays something not related to type?

또 주의할 점이 있는데 10분 더할 때 59분 넘어가는 경우도 생각해야 한다. 9, 17번 테케가 이거 때문에 틀린다.

 

반례

[["05:57", "06:02"], ["04:00", "06:59"], ["03:56", "07:57"], ["06:12", "08:55"], ["07:09", "07:11"], ["04:00", "06:02"]]

4

 

[["08:00", "08:30"], ["08:00", "13:00"], ["12:30", "13:30"]]

2

 

[["00:01", "00:10"], ["00:19", "00:29"]]

2

https://school.programmers.co.kr/questions/44229

https://playground10.tistory.com/293