카카오 호텔 방 배정 : map 을 이용해서 깔끔하게 처리합시다.
카카오 호텔 방 배정 문제를 보겠습니다. 우리는 이 쿼리에 대한 답을 효율적으로 처리해야 합니다. 단, 방의 갯수는 10^12개 이하입니다. 10^12개에 대한 정보를 모두 담을 수는 없습니다. 어떻게 해야 할까요? 대신에 우리는 이런 아이디어를 하나 생각해 볼 수 있습니다. 그러면, 구간 정보를 어떻게 담아야 할까요? 방이 총 5개가 있다고 생각해 보겠습니다. 먼저, 초기 상태는 모든 방이 비어 있을 겁니다. 그러면, [1,5]가 비어 있었다는 정보를 넣습니다. 이제, 3보다 크거나 같은 비어 있는 방 중에서, 가장 작은 번호를 가지는 방을 빼 보겠습니다. 이를 K=3인 쿼리라 하겠습니다. 그러면 이 때 어떻게 나누어 질까요? 구간이 [1,2] [4,5]로 나누어 집니다. 이것을 어떻게 관리해 볼까요?..
자료알고/알고리즘
2020. 5. 9. 15:37
최근댓글