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

프로그래머스

예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

 

풀이 방법

"겹치는 예약"을 찾고 "최대로 겹치는 방의 개수"를 찾아서 출력하면 되는 문제입니다.

 

1. string으로 입력받은 예약 시간을 인덱싱이 가능하도록 int로 바꿔줍니다.

int ttoi(string time, bool isEnd = false)
{
    int ret = isEnd ? 9 : 0; // (청소시간 포함하여 9)
    ret += time[4] - '0';
    ret += (time[3] - '0') * 10;
    ret += (time[1] - '0') * 60;
    ret += (time[0] - '0') * 600;
    return ret;
}

 

종료 시간, 시작 시간 겹침 허용하기에 10이 아닌 9를 더함

 

2. 방이 예약된 시간에 방이 추가 되었다고 체크해주기

for (auto& book : book_time)
{
    int start = ttoi(book[0]);
    int end = ttoi(book[1], true);

    while (start <= end)
    {
        arr[start]++;
        answer = max(answer, arr[start]); ( 가장 많이 겹친 수 )
        start++;
    }
}

 

3. 가장 많이 겹친 수를 출력

return answer;

 

정답 코드

#include <string>
#include <vector>

using namespace std;

int ttoi(string time, bool isEnd = false)
{
    int ret = isEnd ? 9 : 0;
    ret += time[4] - '0';
    ret += (time[3] - '0') * 10;
    ret += (time[1] - '0') * 60;
    ret += (time[0] - '0') * 600;
    return ret;
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    vector<int> arr(9999);
    
    for (auto& book : book_time)
    {
        int start = ttoi(book[0]);
        int end = ttoi(book[1], true);
        
        while (start <= end)
        {
            arr[start]++;
            answer = max(answer, arr[start]);
            start++;
        }
    }
    return answer;
}

 

 

시간 복잡도 해결 코드

#include <string>
#include <vector>

using namespace std;

int ttoi(string time, bool isEnd = false)
{
    int ret = isEnd ? 9 : 0;
    ret += time[4] - '0';
    ret += (time[3] - '0') * 10;
    ret += (time[1] - '0') * 60;
    ret += (time[0] - '0') * 600;
    return ret;
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    vector<int> arr(9999);
    
    for (auto& book : book_time)
    {
        int start = ttoi(book[0]);
        int end = ttoi(book[1], true);
        
        arr[start]++;
        arr[end+1]--;
    }
    
    for (int i = 1; i < 9999; i++){
        arr[i] = arr[i] + arr[i-1];        
        answer = max(answer, arr[i]);
    }

    return answer;
}