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

호텔 방 배정

 

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

 

문제 설명

 

 - "스노우 타운"에서 호텔을 운영하고 있는 "스카피"는 고객들에게 방을 배정하려 한다.

 

 - 호텔 방은 총 K개가 존재하며, 1번 ~ K번까지 번호로 구분하고 있다.

 

 - 처음에는 모든 방이 비어 있다.

 

 - 방 배정 규칙은 다음과 같다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.

2. 고객은 투숙하기 원하는 방 번호를 제출합니다.

3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.

4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

 - 고객이 원하는 방 번호가 순서대로 들어왔을 때 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하라.

 

 

---

 

입력 값

 - 방 번호 k는 1이상 1조 이하의 자연수이다.

 

 - 고객이 원하는 방 번호가 담긴 배열 room_number의 크기는 1 이상 200,000 이하이다.

 

 - room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수이다.

 

 - room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어진다.

 

---

 

 

예제

---

 

문제 분석

 

 - 고객에게 제공되는 방 번호는 1조 이하이기 때문에 int형이 아니라 long long 형을 이용해야 한다.

 

 - 고객에게 어떤 방이 제공 될 지 저장 하기 위해서 unordered_map을 사용해야 한다.

   방이 최대 1조개를 가질 수 있기 때문에 배열로 미리 선언이 불가능하다.

   map은 값 저장 시 매번 정렬을 하는 반면, unordered_map은 해시 함수를 이용하여 저장(정렬x)하기 때문에 더 빠르다.

 

 - 고객이 원하는 방이 이미 다른 고객이 배정되어 있을 때 다음 방을 빠르게 찾기 위하여 유니온 파인드의 방법을 이용한다.

유니온 파인드(Union - Find)

- 초기 모습

 

1번 고객은 2번 방을 배정 받기 원하고, 2번 방은 비어 있기 때문에 배정해준다.

- 방 배열은 2번에 다음 방 번호를 넣는다.

 

2번 고객은 2번 방을 배정 받기 원하지만, 해당 방에는 이미 고객이 존재한다.

- 방 배열에서 2번에는 값(3) 이 존재하기 때문에 해당 값의 방을 실제 배정한다.

- 실제 배정 받은 방(3) 과 원했던 방(2) 모두 실제 배정 받은 방 다음 값(4)으로 변경한다.

 

 

3번 고객은 2번 방을 배정 받기 원했지만, 해당 방에는 이미 고객이 존재한다.

- 방 배열에서 2번에는 값(4) 이 존재하기 때문에 해당 값의 방을 실제 배정한다.

- 실제 배정 받은 방(4) 과 원했던 방(2) 모두 실제 배정 받은 방 다음 값(5)으로 변경한다.

 

 

4번 고객은 3번 방을 배정 받기 원했지만, 해당 방에는 이미 고객이 존재한다.

- 방 배열에서 3번에는 값(4) 이 존재하기 때문에 해당 값의 방을 실제 배정한다.

- 방 배열에서 4번에는 값(5) 이 존재하기 때문에 해당 값의 방을 실제 배정한다.

- 실제 배정 받은 방(5) 과 원했던 방(3, 4) 모두 실제 배정 받은 방 다음 값(6)으로 변경한다.

 

---

 

소스 코드

 

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> m;

long long findRoom(long long n)
{
	if (m[n] == 0)
	{
		m[n] = n + 1;
		return n;
	}
	return m[n]=findRoom(m[n]);
}


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

	for (auto rn : room_number)
	{
		long long frn = findRoom(rn);
		answer.push_back(frn);
	}


	return answer;
}