[2] 호텔 대실 (구현, queue)

문제 설명
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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개의 방이 필요합니다.

---

문제 풀이

시작 시간으로 오름차순 정렬
하나씩 꺼내서 넣을 때, 방이 있는지 체크, 없으면 새로운 queue에 넣기

마지막에 queue의 개수를 세면 된다. (== vec.size())

 

왜인지는 모르겠으나, compare 함수에서

return t2.IsLaterThan(t1); 대신에 return t1.IsLaterThan(t2) == false;

를 사용하면 마지막 테스트케이스에서 segmentFault 오류가 발생한다;;; <- 이거때문에 오래걸렸다.

왠만하면 sort compare 함수에는 그냥 직접 접근하는 방식으로 쓰자.

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

using namespace std;

struct Time
{
	int Hour;
	int Minutes;
	Time()
	{
		Hour = 0;
		Minutes = 0;
	};
	Time(string str)
	{
		int colonPos = str.find(':');
		Hour = stoi(str.substr(0, colonPos));
		Minutes = stoi(str.substr(colonPos + 1));
	}
	bool IsLaterThan(Time t2)
	{
		if (Hour != t2.Hour)
			return Hour > t2.Hour;

		return Minutes > t2.Minutes;
	}
};

bool compare(const vector<string>& s1, const vector<string>& s2)
{
	Time t1(s1[0]);
	Time t2(s2[0]);

    return t2.IsLaterThan(t1);
}

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

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

	vector<queue<Time>> vec;
	for (int i = 0; i < book_time.size(); i++)
	{
		if (vec.empty())
		{
			queue<Time> q;
			q.push(Time(book_time[i][1]));
			vec.push_back(q);
		}
		else
		{
			// 하나씩 꺼내서 넣을 때, 방이 있는지 체크, 없으면 새로운 queue에 넣기
			bool isCan = false;
			for (int j = 0; j < vec.size(); j++)
			{
				queue<Time>* q = &vec[j];
				Time lastEnd = q->front();
				lastEnd.Minutes += 10;
				if (lastEnd.Minutes >= 60)
				{
					lastEnd.Hour += 1;
					lastEnd.Minutes -= 60;
				}

				if (lastEnd.IsLaterThan(book_time[i][0]))
					continue;
				else
				{
					q->pop();
					q->push(book_time[i][1]);
					isCan = true;
					break;
				}
			}
			if (isCan == false)
			{
				queue<Time> tempQ;
				tempQ.push(Time(book_time[i][1]));
				vec.push_back(tempQ);
			}
		}
	}

	answer = vec.empty() ? 0 : vec.size();
	return answer;
}