문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 예약시간이 ["HH:MM", "HH:MM"] 형태로 주어진다.
  • 한번 사용한 객실은 10분간 청소를 하고 다음 손님이 이용할 수 있다.
  • 필요한 최소 객실의 수를 구하여라.



2. 알고리즘 설계

  • priority_queue(pq)를 활용해 greedy 하게 접근



3. 로직

  • 정렬을 위한 구조체 선언

    struct Room{
    int start, end;

    Room(string s, string e) {
    	start = convert_min(s);
    	end = convert_min(e);
    }

    int convert_min(string time) {
    	int hour = (time[0] * 10 + time[1]) * 60;
    	int min = (time[3] * 10 + time[4]) + hour;

    	return min;
    }

    bool operator< (const Room &other) const {
    	return start > other.start;
    }
};
  • pq에서 하나씩 꺼내면서
  • 방이 비었다면, 해당 방의 마지막 시간을 갱신시켜주고,
  • 여유 방이 없다면, 새로운 방을 만들면 된다.


4. 전체 코드

#include <queue>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

struct Room{
	int start, end;

	Room(string s, string e) {
		start = convert_min(s);
		end = convert_min(e);
	}

	int convert_min(string time) {
		int hour = (time[0] * 10 + time[1]) * 60;
		int min = (time[3] * 10 + time[4]) + hour;

		return min;
	}

	bool operator< (const Room &other) const {
		return start > other.start;
	}
};

int solution(vector<vector<string>> book_time) 
{
	priority_queue<Room> pq;

	for (int i = 0; i < book_time.size(); i++) {
		pq.push(Room(book_time[i][0], book_time[i][1]));
	}

	vector<int> v;

	while (!pq.empty()) {
		Room now = pq.top();
		pq.pop();

		bool chk = false;
		for (int i = 0; i < v.size(); i++) {
			if (now.start >= v[i]) {
				v[i] = now.end + 10;
				chk = true;
				break;
			}
		}
		if(!chk)
			v.push_back(now.end + 10);
	}
	
	return v.size();
}


5. 소감

  • 우선순위 큐 관련 문제를 최근에 2문제(과제 진행하기, 광물 캐기) 풀어본 경험으로 쉽게 접근이 가능했다.
  • 역시 PS는 꾸준함과 경험이다…