카카오 호텔 방 배정 : map 을 이용해서 깔끔하게 처리합시다.

 카카오 호텔 방 배정 문제를 보겠습니다. 우리는 이 쿼리에 대한 답을 효율적으로 처리해야 합니다.

 

 단, 방의 갯수는 10^12개 이하입니다. 10^12개에 대한 정보를 모두 담을 수는 없습니다. 어떻게 해야 할까요?

 

 

---

 대신에 우리는 이런 아이디어를 하나 생각해 볼 수 있습니다.

 

 그러면, 구간 정보를 어떻게 담아야 할까요? 방이 총 5개가 있다고 생각해 보겠습니다.

 

 

 먼저, 초기 상태는 모든 방이 비어 있을 겁니다. 그러면, [1,5]가 비어 있었다는 정보를 넣습니다. 이제, 3보다 크거나 같은 비어 있는 방 중에서, 가장 작은 번호를 가지는 방을 빼 보겠습니다. 이를 K=3인 쿼리라 하겠습니다.

 

 

 그러면 이 때 어떻게 나누어 질까요? 구간이 [1,2] [4,5]로 나누어 집니다. 이것을 어떻게 관리해 볼까요?

 

 여기서 구간은 비어 있는 방들을 표현을 합니다. 그러면 k보다 크거나 같은 것 중에서, 비어 있는 방을 어떻게 빠르게 찾을까요?

 

 

---

 아래 그림을 보겠습니다.

 

 

 e(k-1)의 값이 100이였습니다. e(k)의 값이 125였습니다. 방 번호가 103보다 크거나 같으면서, 비어 있는 방 중에서 가장 작은 수는 어떻게 구할까요? 최소한 [?,100] 구간에 있지 않은 것은 확실합니다. 왜냐하면, 100 < 103이기 때문입니다. [??, 125] 구간에는 요구하는 답이 있을까요?

 

 네. [??, 100] 구간의 다음 구간이기 때문입니다.

 

 

 그러면 이 경우에는 어떨까요? e(k-1) = 100이였고, e(k) = 103이였습니다. 빈 방 중에서, 103보다 크거나 같은 방 중 가장 수가 작은 방을 골라야 합니다. 답은 무엇일까요? 103입니다. 103은 비어있기 때문입니다.

 

 

 따라서, mm[e] = s꼴로 저장했다면, upper_bound가 아닌, lower_bound로 찾아야 할 겁니다. 이제 k = 5이고, [3, 5, 3] 순서로 쿼리가 들어왔다고 생각해 보겠습니다.

 

 

 일단 3이 들어왔을 때에는 3입니다. 다음에 5가 들어왔을 때에는 어떤가요? 빈 방의 구간은 [1,2], [4,5]가 있었습니다. 그러면 자료 구조에는, [2] = 1, [5] = 4 이렇게 표현이 될 겁니다. 여기서 2와 5는 key 값을 의미합니다. 5보다 크거나 같은 Key를 찾으면 5이고, 이는 [4,5] 구간을 표현하는 데이터입니다.

 

 

 그렇다면, [4,5] 구간에서 어떠한 작업을 하면 되겠군요. 여기서 5를 점유 되었다고 표시하면 되므로, 그 처리를 하고 난 후에 자료구조는 다음과 같은 정보를 담아야 할 거에요.

 

 

 [4,4]와 [1,2]에 대한 정보를 담으면 됩니다. 키 값이 삽입, 삭제가 되고, x보다 크거나 같은 key를 구하는 쿼리를 빠르게 처리해야 한다. 어떤 것이 있을까요? 동적으로 처리해야 하는 경우에, map이나 set을 쓰는 것이 적합합니다. Java의 Treexxx 계열이나, C++의 STL에서 map, set을 쓴다. 괜찮은 전략입니다. 생각보다 범용적으로 쓰이기도 하고요. 어떤 자료구조를 써야 될 지 모르겠다. 그러면 트리 계열 먼저 생각해 보시는 것도 코테에서는 괜찮은 전략입니다.

 

 

---

 이제 소스코드를 보도록 하겠습니다.

 

 먼저 구간을 관리하는 map을 선언해 주었습니다.

 

 

 다음에, 쿼리가 들어올 때 마다, 후보해가 들어있는 구간을 lower_bound 함수로 뽑아냅니다. 다음에 구간 중에서 답이 되는 값을 뽑아냅니다. 이는 18번째 줄에서 수행합니다. qu가 [s,e]에 포함되지 않는 경우가 문제인데요. qu>e일 리는 없습니다. 왜냐하면, key 값이 e보다 크거나 같은 구간을 뽑았기 때문입니다. 그렇다면 qu < s인 경우인데요. 이 때에는 답이 s가 된다는 것을 잘 처리해야 합니다.

 

 

 [s, e] 구간에서 qu를 선택했다면, 다음에 구간은 [s, qu-1], [qu+1, e]로 쪼개집니다. 따라서, [s, e]에 대한 구간 정보는 지우고, [s, qu-1]과 [qu+1, e]에 대한 구간 정보를 넣으면 됩니다. invaild 한 경우에는 그냥 무시하면 됩니다. 이제 과제 하나를 드리겠습니다. 만약에, C만 사용이 가능하다면 어떻게 이 문제를 해결하실 건가요?