LEVEL3의 표편집 문제와 상당히 유사한 문제입니다.
그 문제에서 약간의 효율성을 추가하면, 충분히 해결할 수 있는 문제입니다.

문제를 요약하자면, 원하는 호텔방이 비어있으면, 해당 방에 배정되지만, 비어있지 않은 경우,
그 보다 호수가 큰 방 중에 가장 먼저 비어있는 방을 배정받게 됩니다.

이 문제의 좋은 점은, 테스트케이스부터 예외처리가 전부 되어있어, 예외상황을 신경쓰지 않아도 됩니다.
문제의 지문에도, 배정이 불가능한 경우는 테스트케이스로 주어지지 않는다고 명시되어 있습니다.
따라서, 예외사항은 걱정하지 말고, 효율성만 신경써서 문제를 풀어내면 됩니다.

k가 10¹² 만큼 존재합니다. 이걸 배열로 만들어서 푸실 분은 존재하지 않을거라 믿습니다.
너무나도 큰 배열이기 때문에, 컴퓨터가 힘들어하지 않을까 싶습니다.
애초부터 호텔 방에 저리 많으면 만수르가 아니지 싶습니다.

사실 문제의 지문만 읽어보아도, k는 함정카드 라는 것을 알 수 있습니다.
사실 문제를 푸는데에 있어서 호텔 방이 전체 몇 개가 존재하는지 알 필요가 없습니다.
room_number에서 요청한 방만 배정해주면 이 문제를 풀 수 있으니까 말이죠.
예외처리가 필요한 케이스가 존재하지 않기 때문에, k는 있으나마나인 것을 눈치채야 합니다.

그럼 room_number배열만 가지고 문제를 풀어야겠군요.
해당 문제는 LinkedList 자료구조를 가지고 문제를 풀 수 있지만,
더 쉽게, Hash 자료구조를 사용해서 푸는 것이 더욱 간단합니다.

각각의 Hash자료구조에는 Key : Value 와 같은 형태를 지니고 있습니다.
저희는 Key값에 현재 방번호, Value값에 비어있는 다음 방번호 와 같이 지정할 예정입니다.
이런 자료구조를 사용하게 되면, 엄청난 메모리 절약이 될겁니다.
공간 절약은 Hash 자료구조를 사용하면 손쉽게 해결 할 수 있습니다.

이젠 시간을 절약해야 합니다.
해당 문제는 최악의 경우, O(N^2)의 시간복잡도를 가지게 되지만,
그래도 최대한 O(N)에 가까워 지게 만들 수 있는 알고리즘이 존재합니다.

O(N) < 이 문제의 시간복잡도 < O(N^2)

사실 저런 시간복잡도는 BigO 체계에서는 정의되지 않았습니다.
그냥 이 문제가 뭐 같은 겁니다.
그래도 굳이 정의하자면 O(N^2)가 이 문제의 시간복잡도가 될겁니다. (물론 최악의 테스트 케이스 일 경우입니다.)
그래서 많은 분들이 분명 O(N^2)으로 문제를 풀어내도, 효율성에서 나가리가 됩니다.

시간 단축의 핵심은 노드의 방문순서에 따라 달려있습니다.
아래는 이 문제의 핵심 알고리즘을 정리하였습니다.

1. for문으로 room_number를 하나씩 불러온다.
2. while문을 씌운다.
3. (if)현재 값이 해시에 값이 없는지 확인한다.
4. (true)해시에 값이 없다면, 배정되지 않은 방이라는 의미이미로, 해시에 값을 (현재 방번호 : 현재 방번호 + 1)와 같이 추가한다.
5. 임시리스트에 저장된 배열이 있다면, 해당 값들을 불러와 다음방번호를 현재 방번호 + 1로 전부 바꿔준다.
6. (break)while문을 탈출한다.
7. (else)해시에 값이 있으면, 배정된 방이므로, 현재 방번호를 해시에 접근하여 다음 방번호를 얻어온다. 또한, 현재 방번호를 임시리스트에 저장한다.

위의 알고리즘을 풀어쓰자면,
해시에는 현재 방번호 : 다음 방번호 라는 형식의 데이터가 추가됩니다.
또한 현재 방번호가 해시에 추가되었다는 의미는, 해당 방번호는 누군가에게 배정되었다는 의미가 됩니다.
그래서 while문에 진입하여 if문에서 현재 방번호가 hash에 있는지 확인합니다.
만약 해시의 key값에 현재 방번호가 존재한다면, false가 되어, else문으로 넘어가게 됩니다.
else문에서는 해시에 접근하여, 다음 방번호를 불러오고, 현재 방번호를 임시리스트에 저장하게 됩니다.
현재 방번호를 따로 저장하는 이유는, 지금까지 방문한, 노드들의 다음 비어있는 방번호는 마지막에 최종적으로 업데이트
되는 다음방번호와 전부 동일하기 때문입니다. 아마 이해가 힘들 것 같으니 예시를 들어봅시다.

k가 5라고 가정하고, 먼저 2번 방요청이 들어왔습니다.
{2:3}
위와 같이 데이터가 추가됩니다. 해시에 존재하는 것이 없었고, 값추가는 항상 '''현재방번호 : 현재방번호 + 1''' 과 같이 추가합니다.
그 다음, 3을 배정합니다.
{2:3, 3:4}
그럼 위와 같이 됩니다. 해시에 3이라는 key값이 존재하지 않았고, 값추가는 위와 같이 하면 현재 해시상태는 위와 같습니다.
근데 여기서 의문이 생기겠지만, 그래도 참고 다음 예시를 봅시다.
그 다음, 2를 배정해봅니다.
{2:5, 3:5, 4:5}
위와 같이 바뀝니다. 해시에는 2라는 key값이 이미 존재하므로 2를 임시리스트에 저장하고, 해시에 자신을 대입하여 다음 방번호인,
3을 불러오게 됩니다. 하지만, 3도 마찬가지로, 이미 존재하므로 3도 임시리스트에 저장하고, 해시에 3ㅇ르 대입하여 다음 방번호인,
4를 불러오게 됩니다. 4는 해시에 존재하지 않았으므로, {4:5}를 추가하고, 기존에 방문했던 해시들도 다시 불러와,
전부 다음 방번호를 똑같이 업데이트 시켜줍니다. 이 행동을 반복하면, 우리는 답을 구해낼 수 있습니다.

여기서 의문점이 들것입니다. 한 번에 업데이트 하는 것하고, 방문한 방번호들만 업데이트하는 것하고 무엇이 다른지 말이죠.
보통은 처음에 코딩할 때는, 값이 추가되면, 추가된 방과 붙어있는 모든 방들을 그 다음 비어있는 방으로 전부 업데이트
하려고 했을 것입니다. 이 부분에서 최악의 시간복잡도와 가까워지기 때문에, 이 문제에서 효율성에서 떨어지게 됩니다.

비슷한거 아닌가? 라고 할 수 있을 것입니다.
전혀 다릅니다. 아마 문제에서 사용한 비슷한 테스트케이스 같아 보이는 것으로 예시를 들어보겠습니다.

k = 10^12 , room_number = [1, 2, 3, ..... , 200000]
위와 같은 경우입니다. 사실 여기에서도 알다시피 room number의 최대 배열제한 20만입니다.
그래서 더욱 확실히 k는 이 문제에서 필요없다는 사실이 드러납니다.
위와 같은 경우에서 room number에서 겹치는 번호없이 방배정 요청이 들어옵니다.
하지만, 인접한 모든 방을 업데이트하는 경우, 위에서 최악의 시간복잡도를 초래하게 됩니다.
하지만, 방문한 방만 추후에 업데이트하는 경우, 시간복잡도에 제일 유리하게 됩니다.
각각 겹치는 해시가 존재하지 않으니, 자기자신만 업데이트하면 되기 때문이죠.

사실 따지고 보면, 값을 먼저 업데이트하느냐, 추후에 업데이트 하느냐의 차이에 따라서 시간복잡도 크게 달라지는 문제입니다.
BFS에서도 문제에서도 visited변수를 처음부터 True로 만드냐 나중에 True만드냐와 비슷한 경우입니다.

답은 산출할 때는, 따로 정답배열을 만들어서 해시에 추가할 때, 같이 추가해서 리턴하시면 됩니다.
해당 해설은 카카오테크해설을 기반으로 재해석한 해설입니다.
아마, 그림이 없어서 이해하기 힘드신 분들은 카카오테크 공식해설을 참고하면 많은 도움이 될겁니다.

2 * 10⁴ ..