[Programmers]2019 카카오 개발자 겨울 인턴십: 호텔 방 배정(C++)/Disjoint Set

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

코딩테스트 연습 - 호텔 방 배정

레벨 4라서 두려움에 떨었던 문제

백준식 풀이법(안풀리면 컨닝)으로 disjoint set이라는 건 알았지만 어떻게 풀지 고민했다

 

그래서 처음에는 0이라는 더미 노드를 만들어서 방이 나올 때 마다 union하고, find해서 parent가 0과 다를 때 새로운 node를 더해주는 식으로 구현했다

하지만 그렇게 구현하니까 브루트포스와 다를게 없었다 ...

그래서 효율성에서 광탈하고 카카오 테크 블로그 풀이를 슬쩍했다

 

이것이 핵심 로직인데 union-find 자료구조의 find 부분을 응용한 부분이 핵심인 것 같당

 

이렇게 빈 방이 있을 경우에는 새로 노드를 만들어서 다음 방을 가리키게 하고

빈 방이 없을 때 에는 재귀적으로 부모 노드를 계속 방문하면서 path를 갱신해준다

 

또한 메모리 초과가 계속 발생했는데 k의 최대값이 10^12이므로 linear array에 저장이 불가능했다

[최대 방 개수]=10^12

[고객이 원하는 방 개수]=200,000

이므로 고객이 원하는 방 개수만큼의 메모리만 필요하다

 

그래서 hashmap(c++에서는 map)을 사용해서 parent를 저장해주면 끝 ~~

코드는 엄청 짧당

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

map<long long, long long> m;

long long func(long long x) {
	if (m.find(x) == m.end()) {
		m.insert(make_pair(x, x + 1));
		return x;
	}
	return m.find(x)->second = func(m.find(x)->second);
}

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

	for (auto x : room_number) {
		answer.push_back(func(x));
	}
	return answer;
}