[프로그래머스] 64063. 호텔 방 배정

2019 카카오 개발자 겨울 인턴십 - 64063. 호텔 방 배정

Python 풀이

 

풀이

Union-Find 알고리즘을 이용하여 풀면 될 것이라고 직감이 왔다.

[백준] 10775. 공항 문제와 굉장히 유사했기 때문.

 

그런데 이제, 효율성을 위해 알고리즘을 조금 바꿀 필요가 있었다.

Find는 그대로 두지만, Union하는 과정에서,

무조건 숫자가 높은 쪽이 root가 되도록 하는 것.

 

그렇게 하고, n번의 방이 찰 때마다,

n과 n+1을 Union하는 방식으로 진행한다.

 

이 예시에서는,

k = 10
room_number = [1,3,4,1,3,1]

맨 처음엔 dictionary가 이 상태일 것이다.

{1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}

1~3번째 손님에게 방을 주어 1, 3, 4번 방을 채우면, 아래와 같은 상황이 된다.

{1: 2, 2: 2, 3: 4, 4: 5, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}

이후, 4번째 손님의 방을 줄 때는, find(1)을 수행하면 결과값이 2이므로, 2번 방에 투숙시킨다.

{1: 2, 2: 3, 3: 4, 4: 5, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}

5번째 손님은 find(3)을 수행하면, 결과값이 5이므로, 5번 방에 투숙시킨다.

{1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}

마지막으로 6번째 손님은, find(1) == 6이므로, 6번 방에 투숙시키면 된다.

{1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10}

(Find, Union과정에서의 간소화는 무시하였음)

 

전체 Code

import sys
sys.setrecursionlimit(10000)
 
def solution(k, room_number):
    room = {i: i for i in range(1, k+1)}
 
    # Union-Find 구현
    def find(x):
        if room[x] == x:
            return x
 
        k = find(room[x])
        # Union-Find -> Root까지의 경로 압축 (line 13)
        room[x] = k
        return k
 
 
    # union(n, n+1)로만 사용
    def union(x, y):
        rootX = find(x)
        rootY = find(y)
 
        room[rootX] = rootY
 
 
    # 시작
    answer = []
    for p in room_number:
        root = find(p)
        answer.append(root)
        if root == k:
            continue
        union(root, root+1)
    
    return answer

 

아래 코드는 find연산에서 재귀 횟수 초과 방지를 위함.

import sys
sys.setrecursionlimit(10000)

 

이렇게 풀었더니, 효율성 5, 6, 7번에서 시간 초과가 났다.

조금 더 시간을 단축할 방법을 모색.

 

 

풀이 2

여러 시도를 해봤고,

room = {i: i for i in range(1, k+1)}

으로 맨 처음에 초기화를 시켜준 것이 효율성에 문제가 있었다.

 

이를 없애고, 빈 dictionary에서 시작하여

빈 방(존재하지 않는 Node)를 만났을 때 Node를 만들어 주면서 진행하는 것으로 코드 변경.

그렇게 했더니 성공했다.

 

전체 Code

import sys
sys.setrecursionlimit(10000)
 
def solution(k, room_number):
    room = {}
    # Find 구현
    def find(x):
        if x not in room.keys():
            room[x] = x+1
            return x
 
        if room[x] == x:
            return x
 
        k = find(room[x])
        # Union-Find -> Root까지의 경로 압축 (line 13)
        room[x] = k
        return k
 
 
    # 시작
    answer = []
    for p in room_number:
        if p not in room.keys():
            room[p] = p+1
            answer.append(p)
        else:
            root = find(p)
            answer.append(root)
 
    return answer