[프로그래머스/C++] 호텔 대실

호텔 대실

문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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 <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int ChangeTimeToMinutes(string time)
{
	int h = stoi(time.substr(0, 2));
	int m = stoi(time.substr(3, 2));

	return (h * 60) + m;
}

int solution(vector<vector<string>> book_time) {
	vector<pair<int, int>> room;
	for(int i = 0; i < book_time.size(); i++)
		room.emplace_back(ChangeTimeToMinutes(book_time[i][0]), ChangeTimeToMinutes(book_time[i][1]) + 10);

	sort(room.begin(), room.end());

	int roomCnt = 0;
	vector<pair<int, int>> useRooms;
	for (int i = 0; i < room.size(); i++)
	{
		vector<pair<int, int>> temp;
		for(int j = 0; j < useRooms.size(); j++) // 방 시작 시간마다 사용중인 방들과 겹치는지 검사
		{
			// 대실 시간이 겹쳐진다면, 방 개수 배열에 추가
			if (room[i].first < useRooms[j].second)
				temp.push_back(useRooms[j]);
		}

		useRooms = temp;
		useRooms.push_back(room[i]); // 현재 방은 대실 룸에 추가
		roomCnt = max(roomCnt, (int)useRooms.size());
	}

	return roomCnt;
}

 

⏱️ ChangeTimeToMinutes 함수

ChangeTimeToMinutes 함수는 HH:MM의 형식으로 되어있는 숫자를 분 단위로 전부 바꾸어 int형으로 반환시켜주는 역할을 수행하도록 작성하였다.

 

01:30같은 시간을 0130 이라는 숫자로 변경해도 되지만, 60분이 지났을 때 시간 단위를 +1 하는 처리가 귀찮아서 전부 분 단위로 바꾸어 처리하였다.

 

따라서 1시간은 60분이므로 시간 * 60 + 분을 이용해 구하였다.

 

💻 solution 풀이

문제의 핵심 풀이 과정은 다음과 같이 진행하였다.

 

1. 객실을 사용하는 시간이 빠른 순서대로 정렬한다. (오름차순 정렬)

2. 첫번째 방부터 검사하는 for문을 수행하면서, 현재 사용중인 방(useRooms 벡터) 변수안에 있는 방들과 시간을 비교한다.
    2-1. 만약 현재 객실의 사용 시간이, 사용중인 객실의 끝나는 시간보다 작다면 -> 시간이 겹치는 상황이므로 추가적인 객실이 필요하다. (temp.push_back(useRooms[j])

3. 사용중인 방 vector는(useRooms) 겹치는 시간을 전부 검사한 뒤, 현재 사용하려는 방을 추가한 뒤 vector의 개수를 센다.

4. 이때, 방의 최대 개수가 모든 방을 수용하기 위한 객실 개수이므로, max 함수를 사용하여 구한다.

---

처음에는 문제를 풀이할 때, 객실의 사용시간이 아닌 끝나는 시간을 기준으로 정렬하였다.

그러나, 빨리 사용이 끝나는 객실부터 검사를 수행하면 최적의 객실 배치가 나오지 않기 때문에 객실을 사용하는 시간을 기준으로 다시 정렬한 것이다.

 

객실 사용이 끝나는 시간으로 기준하는것은, 비슷한 "디스크 컨트롤러(프로그래머스)"문제나 "회의실 배정(백준)"같은 문제가 있었던 것 같다.

오히려 그 문제들을 풀어봐서 이 문제도 비슷한 유형일거라 생각했는데 조금은 다른 유형이라 헷갈렸다.

---

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

프로그래머스