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

프로그래머스 호텔 방 배정 풀이입니다.

호텔 방 배정

이 문제는 대표적인 Union-Find문제이다. 그 당시엔 절대 못푼 문제이지만 이후 union-find에 대한 개념을 잡으며 공부를 하고 나니 문제가 풀리게 되었다.

방법은 다음과 같다.

1. 원하는 방 번호 배정이 가능할 경우 그 위치 방으로 들어간 뒤 비어있으면 배치를 해준다. 이후엔 그 방 번호에 다음 방 번호를 가리키게 한다. -> 여기서 find를 사용하여 빈방을 찾아준다.
2. 원하는 방에 배정이 불가능할 경우 원하는 방 번호 find를 해준 뒤 가능한 방 번호를 찾아서 그 방에 할당해준다.

예시를 참조해보면 원하는 방번호는 다음과 같이 들어온다. 1,3,4,1,3,1

우선 처음에 1번 방이 비어있기 때문에 1번방에 1번 손님이 할당된다. 이후 그 1번방이 가리키는 방은 2번방으로 업데이트가 된다.

2번 손님이 원하는 3번 방은 비어있기 때문에 할당이 되고 3번방이 가리키는 방은 4번방으로 업데이트된다.

3번 손님이 원하는 4번 방은 비어있기 때문에 할당이 되고 4번방이 가리키는 방은 5번방으로 업데이트된다.

4번 손님이 원하는 1번 방은 1번손님한테 할당됬기 때문에 1번방이 가리키는 2번방에 할당된다. 이후 2번방이 가리키는 방 번호는 3번으로 업데이트된다.

5번 손님이 원하는 3번 방은 이미 손님이 있기 떄문에 3번방이 가리키는 4번방으로 이동한다. 4번방도 이미 차있기 때문에 4번방이 가리키는 5번방으로 이동한다. 5번방이 비어있기 때문에 5번방에 할당되고 5번방이 가리키는 방번호는 6번으로 업데이트된다.

이와 같이 반복해서 할당된 방 번호를 찾아가는 것이다.

Map의 활용과 Union-Find의 개념을 다시 잡을 수 있게된 계기가 되었다.

#include <string>
#include <vector>
#include <map>
using namespace std;

map<long long, long long> m;

long long find(long long u) {
	if (!m[u]) return u;
	return m[u] = find(m[u]);
}

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

	for (int i = 0; i < room_number.size(); i++) {
		long long cur = room_number[i]; // 원하는 방 번호 배정이 가능할 때 
		if (!m[cur]) {
			answer.push_back(cur);
			m[cur] = find(cur + 1);
		}
		else {
			long long tmp = find(cur);
			answer.push_back(tmp);
			m[tmp] = find(tmp + 1);
		}
	}

	return answer;
}

오늘의 교훈

• Union-Find가 요즘 코테에 자주 나오니까 공부 하자.
• 설명 진짜 못한다..
• 코테 문제는 많이 풀어보자.

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이