1. 풀이

방법 1 - 카운팅 배열 활용

어쨋든 동시에 이용시간이 겹치는 횟수 = 필요한 방의 개수 이다.
따라서 이용 시간에 해당되는 경우마다 카운팅배열에 ++ 해주면, 배열의 최댓값이 결국 필요한 방의 개수이다.

코드가 날라갔다..ㅠ

시간복잡도는 O(n) 이다.

방법 2 - 우선순위 큐 활용

사람의 사고 과정을 생각해보자.

우린 가장 일찍 대실이 시작되는 방 부터, 방을 배정해주고 이후에 그 다음 방, 그 다음 방을 배정해준다. 그리고 배정하기전에 항상 대실이 끝난 방이 있는지 확인해준다.

이런 사람의 사고 과정을 그대로 구현하면된다.

• 우린 가장 일찍 대실이 시작되는 방 부터 -> sort로 book_time을 정렬
  • 2차원 벡터도 알아서 오름차순으로 정렬됨
• 방을 배정해주고 -> 우선순위 큐에 해당 방의 대실 마감시간을 넣어줌
• 그리고 배정하기전에 항상 대실이 끝난 방이 있는지 확인 -> 우선순위 큐의 top과 이번에 받을 예약의 시작 시간을 비교해서, top이 시작 시간보다 작으면 이미 대실 마감이니 pop()해줌

이때, 청소 시간이 항상 10분 있으므로 대실 마감시간은 원래 마감시간 + 10 으로 생각해야함.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;



int get_min(const string & input, string delimiter) {
    auto start=0;
    auto end = input.find(delimiter);
    vector<int> result;
    while(end != string::npos) {
        result.push_back(atoi((input.substr(start, end-start)).c_str()));
        start = end + delimiter.size();
        end = input.find(delimiter, start);
    }
    result.push_back(atoi((input.substr(start)).c_str())); 
    return result[0]*60+result[1];  
}

priority_queue<int, vector<int>, greater<int>> q;
int ret = -1;
int solution(vector<vector<string>> book_time) {
    int answer = 0;
    
    sort(book_time.begin(), book_time.end());
    for(auto it : book_time) {
        int start = get_min(it[0],":");
        int end = get_min(it[1],":") + 10;
        while(q.size() && q.top() <= start) {
            q.pop();
        }          
        q.push(end);
        ret = max(ret, (int)q.size());
    }
    
    return ret;
}

시간복잡도는 O(nlogn) 이다.

2. 오답노트

(1) 우선순위 큐 개념과 연결 실패

매번 작은걸 확인해야함은 감 잡았지만..작은 걸 확인한다 -> 우선순위 큐 사용 으로 개념을 연결짓지 못했고, 결국 우선순위 큐를 사용하지 못했다.

다음부터 작은걸 확인해야하는 경우에는 우선순위 큐를 활용해서 풀 수 있을지 꼭 확인해봐야겠다.

(2) 이차원 벡터 sort

처음에 "sort() 해볼까?" 싶었는데 sort로 이차원 벡터도 정렬이 된다는 것을 몰랐다.

vector<vector<int>> 정렬

vector<vector<int>> v = {
    {2, 3},
    {1, 5},
    {1, 2}
};
sort(v.begin(), v.end());

{1, 2}
{1, 5}
{2, 3}

vector<vector<string>> 정렬

vector<vector<string>> v = {
    {"15:00", "17:00"},
    {"09:10", "10:10"},
    {"10:20", "12:20"}
};

sort(v.begin(), v.end());
{"09:10", "10:10"}
{"10:20", "12:20"}
{"15:00", "17:00"}