문제

[프로그래머스][Python][2019 카카오 개발자 겨울 인턴십] 호텔 방 배정

---

풀이

연속된 숫자의 묶음을 하나의 집합처럼 다뤄야 한다는 생각은 금방 떠올릴 수 있었다.
그래야만 중복된 번호를 요청할 때 '해당 번호보다 큰 번호 중 아직 배정되지 않은 방의 번호' 를 반복문을 돌지 않고도 찾을 수 있을테니까.

그런데 그 방법을 찾기까지가 오래 걸렸다..

첫번째 방법

처음에는 딕셔너리를 이용해서
key를 연속된 숫자 묶음의 첫번째 수(가장 작은 수)
value를 같은 묶음의 마지막 수(가장 큰 수)로 저장하고,
이분 탐색을 통해 집합을 추가하고,
만약 새로 추가된 번호로 인해 기존의 집합이 변형되면 이를 수정하는 방식으로 구현하려고 하였으나 시간 초과가 발생했다.

2번째 방법(성공)

크루스칼 알고리즘의 유니온 파인드와 유사한 방식으로 이를 개선했다.
기존의 집합을 변형하기 위해 딕셔너리의 값을 수정하고 제거할 필요 없이,
연속된 숫자 집합의 모든 수들이 마지막 수의 다음 수를 가르키도록 했다.
예를 들어, k = 6이고, 1, 2, 3, 4 가 사용되었다면
next[1] = 5
next[2] = 5
next[3] = 5
next[4] = 5
가 저장된다.

이 방법은 유니온 파인드에서 부모 노드를 저장하는 배열을 갱신할 때
루트 노드만을 저장하게 하는 방법과 유사하다.
이 풀이 또한 재귀 호출을 통해서
같은 집합 내의 모든 숫자들이 전체 집합의 다음 수를 가르키게 할 수 있었다.

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)


def solution(k, room_number):
    answer = []
    next_room = defaultdict(int)
    for i in range(len(room_number)):
        answer.append(find_next(next_room, room_number[i]))
    return answer


def find_next(next_room:defaultdict, number):
    next_num = next_room[number]
    
    # 다음 수가 없다면, 처음 사용되는 수 이다.
    if next_num == 0:
        next_room[number] = number + 1
        return number
    
    # 다음 수가 있다면, 재귀를 통해 해당 집합의 마지막 수를 갱신한다.
    next_room[number] = find_next(next_room, next_num)
    
    # 갱신된 집합의 마지막 수를 반환한다.
    return next_room[number]