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

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

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

접근 0

#include <string>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

set<ll> hotel;

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

	for (ll i = 1LL; i <= k; ++i) {
		hotel.insert(i);
	}


	for (int i = 0; i < room_number.size(); ++i) {
		ll room = room_number[i];

		auto iter = hotel.find(room);
		if (iter != hotel.end()) {
			answer.push_back(room);
			hotel.erase(iter);
		}
		else {
			iter = hotel.upper_bound(room);
			answer.push_back(*iter);
			hotel.erase(iter);
		}

	}

	return answer;
}

접근 1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

//parent[i]: i번보다 번호가 크고, 배정 가능한 방 중 가장 번호가 작은 방의 번호
//parent[i] = i일 경우 방 배정 가능 -> 방 배정 후 parent[i] = i+1
vector<ll> parent;


//u가 속한 트리의 루트 번호 반환
ll find(ll u) {
	//부모가 자기 자신을 가리키는 경우 u는 루트 노드
	if (u == parent[u]) return u;

	//경로 압축(path compression) 최적화 구현
	return parent[u] = find(parent[u]);
}

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

	for (ll i = 0; i < k; ++i)
		parent[i] = i;
	
	for (int i = 0; i < room_number.size(); ++i) {
		ll roomNum = room_number[i] - 1;
		
		if (parent[roomNum] == roomNum) {
			answer.push_back(roomNum + 1);
			parent[roomNum] = roomNum + 1;
		}
		else {
			ll availableNum = find(roomNum);
			answer.push_back(availableNum + 1);
			parent[availableNum] = availableNum + 1;
		}
	}

	return answer;
}

접근 2

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

typedef long long ll;

//parent[i]: i번보다 번호가 크고, 배정 가능한 방 중 가장 번호가 작은 방의 번호
//parent[i] = i일 경우 방 배정 가능 -> 방 배정 후 parent[i] = i+1
unordered_map<ll, ll> parent;


//u가 속한 트리의 루트 번호 반환
ll find(ll u) {
	//부모가 자기 자신을 가리키는 경우 u는 루트 노드
	if (u == parent[u]) return u;

	//경로 압축(path compression) 최적화 구현
	return parent[u] = find(parent[u]);
}

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

	for (ll i = 0; i < k; ++i)
		parent.insert({ i, i });
	
	for (int i = 0; i < room_number.size(); ++i) {
		ll roomNum = room_number[i] - 1;
		
		if (parent[roomNum] == roomNum) {
			answer.push_back(roomNum + 1);
			parent[roomNum] = roomNum + 1;
		}
		else {
			ll availableNum = find(roomNum);
			answer.push_back(availableNum + 1);
			parent[availableNum] = availableNum + 1;
		}
	}

	return answer;
}

풀이

#include <vector>
#include <unordered_map>

using namespace std;

typedef long long ll;

unordered_map<ll, ll> notEmptyRoom;

ll findEmptyRoom(ll u) {
	if (notEmptyRoom.find(u) == notEmptyRoom.end()) return u;

	//경로 압축(path compression) 최적화 구현
	return notEmptyRoom[u] = findEmptyRoom(notEmptyRoom[u]);
}

vector<ll> solution(ll k, vector<ll> room_number) {
	vector<ll> answer;
	
	for (int i = 0; i < room_number.size(); ++i) {
		ll roomNum = room_number[i];
		
		if (notEmptyRoom.find(roomNum) == notEmptyRoom.end()) {
			answer.push_back(roomNum);

			notEmptyRoom[roomNum] = findEmptyRoom(roomNum + 1);
		}
		else {
			ll emptyRoomNum = findEmptyRoom(roomNum);
			answer.push_back(emptyRoomNum);

			notEmptyRoom[emptyRoomNum] = findEmptyRoom(emptyRoomNum + 1);
		}
	}

	return answer;
}

📌참고자료

• c++ unordered_map 사용법
  https://doh-an.tistory.com/5

• 프로그래머스 호텔 방 배정 풀이
  https://ansohxxn.github.io/programmers/138/