[프로그래머스] 호텔 방 배정

링크

https://programmers.co.kr/learn/courses/30/lessons/64063

프로그래머스

풀이

 

각 고객에게 배정되는 방 번호를 순서대로 배열에 담는 문제이다.

 

아마 union_find (disjoint_set) 알고리즘을 알고 계신 분들은 문제 접근에 어려움이 없지 않았을까 라는 생각을 했습니다.

 

일단 전체 방의 개수가 k개인데 k는 10의 12 제곱 이하이다.

그러므로 방의 개수대로 배열을 만드는 것은 불가능하다는 것을 알 수 있다.

 

그래서 map을 이용하여 고객이 배정받은 방을 저장할 수 있도록 합니다.

 

이제 map을 이용하여 현재 고객이 원하는 x위치의 방이 비어 있다면 배정을 해주고

다음에 x방을 원하는 고객이 있을 수 있으니 x방을 선택했을 때 x + 1 변방으로 배정하도록 합니다.

 

먼저 원하는 방이 비어 있을 때입니다. (이해를 돕기 위해 총 10개의 방을 미리 표로 만들었습니다).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

두 개의 표에서

첫 번째 표는 다음 고객이 방을 선택했을 때 배정받는 방 번호를 나타낸 표입니다.

두 번째 표는 현재 고객이 배정받은 방을 나타내는 표입니다.

 

 

이제 원하는 방이 배정되어 있을 때입니다.

 

4번 고객은 2번 방을 선택하였지만 이미 2번은 배정이 되어 있습니다.

그래서 1 + 1 = 2번 방 확인해 보았는데 2번 방은 현재 비어 있어 2번 방을 배정받도록 합니다.

 

5번 고객은 3번 방을 선택하였지만 이미 3번 방은 배정이 되어 있습니다.

그래서 3 + 1 변방인 4번방을 배정 받으려 하였는데 4번방 역시 배정이 되어 있었고 

그래서 4 + 1 번방인 5번은 비어 있어 5번을 배정받도록 합니다.

 

 

마지막 6번 고객은 1번 방을 선택하였지만 이미 1번 방은 배정이 되어 있습니다.

그래서 위의 과정과 같이 비어 있는 방을 찾아보니 6번 방을 배정받게 되었습니다.

이로써 모든 고객의 방을 배정하게 되었습니다.

 

 

그런데 여기서 모든 고객이 모두 1번 방을 원하게 된다면 1번부터 계속 탐색을 해서 비어 있는 방을 찾게 되면 시간적 낭비가 되게 될 것입니다. 

 

예를 들어 4번 고객은 2번 방을 배정 받았고 2번방을 선택할 때 배정받는 방이 3번인데 3번 역시 비어 있지 않고 4번도 비어 있지 않아 결국 5번을 배정받도록 해야 합니다.

 

위의 경우처럼 선택한 방에서 비어 있는 방까지 탐색을 하며 지나가게 되는 방이 배정해야 되는 방 번호를

모두 비어 있는 방 번호로 지정하도록 하여 탐색을 줄이도록 하였습니다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

map<ll, ll> parrent;
ll _find(ll a) {
	if (parrent[a] == 0)
		return a;
	if (parrent[a] != a) {
		return parrent[a] = _find(parrent[a]);
	}

	return parrent[a];
}

vector<long long> solution(long long k, vector<long long> room_number) {
	vector<long long> answer;

	for (ll room : room_number) {
		ll next = _find(room);
		answer.push_back(next);
		parrent[next] = _find(next + 1);
		parrent[room] = parrent[next];

	}
	return answer;
}