[2019 카카오 겨울인턴십] 호텔 방 배정

프로그래머스에 공개된, 2019 카카오 겨울인턴십 호텔 방 배정 문제입니다.

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

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정받은 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

[제한사항]

k는 1 이상 10^12 이하인 자연수입니다.
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
- 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

생각한 아이디어

처음에는 보고 단순히 반복문을 사용해서 구하면 될 것 이라는 생각을 했습니다.

그런데 이 문제는 효율성도 판단하고 있었습니다.

즉, 제한 사항에서 방의 갯수인 k가 최대 10^12 까지 가능했고, 이것을 일반적인 for문으로 앞에서부터 하나씩 계속 비교해 나간다면 연산 횟수도 많아질 것이 분명합니다.

이 문제에서는 부모 노드를 활용한 union & find 개념을 사용해야, 효율성 문제를 통과할 수 있습니다.

STL의 map을 활용하면, 비어있는 방과 그렇지 않은 방을 쉽게 구분할 수 있습니다.
- {key, value} 쌍으로 이루어진 map은 key가 방번호의 역할을 대신할 수 있습니다.
- 여기에 value는, 그 방의 부모 노드 방 번호로 생각합니다.
- 방이 비어있을 경우는 즉시 방을 배정하지만, 방이 비어있지 않을 경우에는 그 다음 방들을 살펴봐야 합니다.
- 여기에서 아이디어를 얻어, 만약 1번 방에 배정하고 난 뒤에는, 1번 방의 부모 노드를 그 다음 방인 2번 방으로 표기합니다.
- 이렇게 되면, 나중에 또 1번 방에 배정받고 싶어하는 사람은 1번 방의 부모 노드 값을 참조하여 그곳으로 바로 가면 됩니다. 즉, 일일이 하나씩 앞에서부터 비교할 필요가 없어집니다.
Union & Find 에 대해 살펴보기 : https://chanhuiseok.github.io/posts/algo-33/

#include <string>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;

map<long long, long long> room;

ll Find(ll num) { // 일종의 collapsing & Find
	// 방이 비어있으면 num을 그대로 반환
	if (room[num] == 0)
        return num;
    else
		return room[num] = getEmpty(room[num]);
}


vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
	
	for (ll num= 0; num < room_number.size(); num++) {
		ll empty = Find(room_number[num]);
		answer.push_back(empty);
		room[empty] = empty + 1;
	}

	return answer;
}

TIP
- C++에서 map 을 전역으로 선언하면, key값이 없는 것을 참조할 때 value = 0으로 반환합니다.
  - 이를 유용하게 활용한 것이 위의 코드입니다.
- vector는 어디에 선언하더라도 내부에 값이 없으면 참조 시 오류를 내는 것과는 다릅니다.
이 문제는 단순히 나와 내 다음 노드를 부모로 설정하는 것 뿐만 아니라, find 연산으로 가고자 하는 방의 부모 노드를 탐색할 때 collapsing find(경로 압축)으로 내 위의 모든 노드들을 지나가면서 최상위 부모 노드에 연결시켜 줘야 나중에 탐색 효율을 높일 수 있습니다.

문제에서 내 다음 노드를 부모로 설정한다면 위와 같은 상황이 될 것인데, 이는 나중에 find를 할 때 최악의 시간복잡도를 가질 수 있는 구조입니다.

따라서 find 연산을 진행할 때마다 재귀적으로 그 이전의 노드들의 부모 노드를 모두 맨 위 루트 노드로 연결시켜 주는 경로 압축을 진행합니다.
이렇게 하면 나중에 1번 방을 배정받고 싶은 사람이 나올 경우, 1번의 부모 노드는 바로 4 이므로 1-2-3-4 를 거치지 않고 바로 4로 향한 뒤 진행할 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

[2019 카카오 겨울인턴십] 호텔 방 배정