프로그래머스 2023.08.30 (2Lv 호텔 대실)

프로그래머스

문제

---

문제 설명
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
   ◈ 1 ≤ book_time의 길이 ≤ 1,000
        ◈ book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
            ◈ [대실 시작 시각, 대실 종료 시각] 형태입니다.
        ◈ 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
            ◈ 예약 시각이 자정을 넘어가는 경우는 없습니다.
            ◈ 시작 시각은 항상 종료 시각보다 빠릅니다.

입출력 예

book_time	result
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

입출력 예 설명
입출력 예 #1
아래 사진과 같습니다.

입출력 예 #2
첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.

입출력 예 #3
세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.

코딩

---

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

using namespace std;

bool compare(vector<string> A, vector<string> B)
{
    int iAhour = stoi(string(A[0].begin(), A[0].begin() + 2));
    int iAmin = stoi(string(A[0].end() - 2, A[0].end()));

    int iBhour = stoi(string(B[0].begin(), B[0].begin() + 2));
    int iBmin = stoi(string(B[0].end() - 2, B[0].end()));

    if (iAhour == iBhour)
    {
        return iAmin < iBmin;
    }
    else
    {
        return iAhour < iBhour;
    }
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;

    vector<string> vecgroup = {};

    sort(book_time.begin(), book_time.end(), compare);

    for (size_t i = 0; i < book_time.size(); ++i)
    {
        bool bNeedGroup = true;
        int idx = -1;

        if (vecgroup.empty())
        {
            vecgroup.push_back(book_time[i][1]);
        }
        else
        {
            int iCheck_hour = stoi(string(book_time[i][0].begin(), book_time[i][0].begin() + 2));
            int iCheck_min = stoi(string(book_time[i][0].end() - 2, book_time[i][0].end()));

            for (size_t j = 0; j < vecgroup.size(); ++j)
            {
                int iGroup_hour = stoi(string(vecgroup[j].begin(), vecgroup[j].begin() + 2));
                int iGroup_min = stoi(string(vecgroup[j].end() - 2, vecgroup[j].end())) + 10;
                
                if (iGroup_min >= 60)
                {
                    iGroup_min -= 60;
                    iGroup_hour += 1;
                }
                
                if (iCheck_hour == iGroup_hour)
                {
                    if (iCheck_min >= iGroup_min)
                    {
                        bNeedGroup = false;
                        idx = j;
                        break;
                    }
                }
                else
                {
                    if (iCheck_hour > iGroup_hour)
                    {
                        bNeedGroup = false;
                        idx = j;
                        break;
                    }
                }
            }

            if (bNeedGroup)
            {
                vecgroup.push_back(book_time[i][1]);
            }
            else
            {
                vecgroup[idx] = book_time[i][1];
            }
        }
    }

    answer = vecgroup.size();

    return answer;
}

문제를 보고 바로 떠올린 것은 이전에 했던 미사일 요격 시스템 문제 풀이었다.

때문에 호텔의 체크인 시간을 오름차순으로 정렬을 해준 뒤, 시간을 비교해가며 문제를 풀어주었다.

 

정렬 시 compare() 함수를 만들어서 직접 정렬을 해주었는데, 이때 시가 같다면 분을 기준으로 정렬해주었다.

 

처음에 10분이라는 청소시간을 고려하지 않았기 때문에 예시로 주어진 테스트는 통과했으나, 실제 테스트 진행시 실패가 많이 떴었다.

뿐만아니라 10분을 더해주는 함수를 만들어 함수 내에서 새로운 시간 문자열을 만들어 반환해 주었더니 core에러가 발생했었다.

아마 함수를 동작하면서 만들어지는 문자열이 너무 많아져 문제가 되는 것 같다. (주어지는 문자열의 수가 1000개 까지 될 수 있기 때문인 듯 하다.)

때문에 따로 문자열을 만들지 않고, for문 내에서 처리해주도록 변경했다.

 

또 이런 방식을 이용하면, 문제를 푸는 속도가 느리다 생각되어 보다 효율적인 방법을 찾기 위해 공부를 해야할것 같다.

실행 결과

---