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

프로그래머스

 

📄 문제

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

 

📝 풀이

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

using namespace std;

int getTime(string format)
{
	return stoi(format.substr(0, 2)) * 60 + stoi(format.substr(3, 2));
}

int solution(vector<vector<string>> book_time) {

	// pair에 입실, 퇴실(청소 시간 포함)을 삽입
	vector<pair<int, int>> v;
	for (vector<string> s : book_time)
		v.push_back({ getTime(s[0]) , getTime(s[1]) + 10 });

	// 정렬 수행(입실 시간 오름차순)
	sort(v.begin(), v.end());

	// 우선순위 큐를 이용하여 검사
	priority_queue<int> q;
	for (int i = 0; i < v.size(); ++i)
	{
		// 큐에서 v[i].first(입장 시간)이 q.top 이상이라면?
		if (!q.empty() && -q.top() <= v[i].first)
			q.pop(); // 동일한 방을 사용 가능하기에 pop을 하여 큐에서 제거

		// 새로운 방 사용 (pop을 한 경우 호출되는경우에는, pop을 한 방을 청소 후 재사용
		q.push(-v[i].second);
	}

	// 큐의 size가 최소로 사용해야하는 방의 개수
	return q.size();
}

• 우선순위 큐를 사용하여 문제를 해결합니다.
• v를 정렬하여 입실시간을 오름차순으로 큐에 삽입할 수 있도록 하였습니다.
• 큐에 지속적으로 삽입하되, top에 있는 값이 v[i].first(입실시간) 이하라면, 해당 방은 사용이 완료된 후 청소를 마치고 재사용할 수 있는 방입니다. 그렇기에 pop을 하여 해당 방을 제거합니다.
  • 그 후에 지속적으로 큐에 삽입하여, 방을 재사용하는것을 확인할 수 있습니다.
• q.size()가 현재 사용중인 방의 개수로 정답을 리턴합니다.