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

아이디어 도출 방법

나는 힌트를 k와 room_number의 숫자 차이로 알았다. k의 max는 10^12지만, room_number는 최대 20만이기 때문이다. 

 

다음으로는 방의 점유 여부를 표시하기 위해서 해당 room_number을 key로 하고 value는 [점유여부, 다음 방 번호]를 가지는 dict 클래스를 생성했다.

 

해당하는 방 번호에 사용자가 있는지 확인하는 방법은 두 가지가 있다. 

• 최대 O(K)만큼 돌면서 dict [room_number]을 호출하는 방식
• union find 알고리즘을 사용해 O(1)에 확인하는 방법

이번 문제의 KEY는 union find short path 알고리즘을 아느냐가 제일 중요했다. 

 

Union Find short path 

문제에서 초기 상태는 아래와 같이 구성된다. 

여기서 세 번의 연산을 수행하게 되면 아래와 표가 아래와 같이 변한다. 이제는 사용자가 원하는 방번호에 배정을 해줄 수 없는 상태가 된다. 여기에서 다음 방 번호를 빨리 찾기 위해서는 사용자가 원하는 방번호에서 다음 방 번호에 접근해 점유 여부를 확인한 후 사용자에게 방을 배정할 수 있다. 

아래 표는 네 번째 연산(문제의 표에서 4번째 줄)을 수행했을 때의 결과인데와 같이 체인형태로 다음 방을 탐색할 수 있는데, 단순히 아래와 같이 접근하게 된다면 최악의 경우에는 O(k)연산이 수행된다. 따라서 경로를 압축하는 형태가 필요해진다 

 

아래 표는 네 번째 연산(문제의 표에서 4번째 줄)을 수행했을 때의 결과인데 경로가 압축된 모습을 확인할 수 있다. 다음 사용자가 3번을 요청해도 4번으로 가는 것이 아니라 6번으로 직행해 방을 배정해줄 수 있게 된다. 이러한 연산이 경로 압축이라고 불린다. 

이제 경로를 압축하는 코드를 확인해 보자면

#1번 부분을 확인하면 요청한 방의 점유 여부를 체크한다. 

#2번에서 방이 사용되고 있지 않다면 해당 방 번호를 리턴해준다.

#3번에서는 해당 방이 사용 중이면 해당 방의 다음 방 번호로 접근해 준다.

#4에서 실질적인 경로 압축이 수행되고 최종적으로 비어있는 방 번호를 리턴해준다. 

def get_next_room_number(rooms, room_number):
    is_occupancy, next_room_number = rooms.get(room_number, [False, room_number]) #1

    if not is_occupancy: #2
        return room_number
    else:
        next_room_number = get_next_room_number(rooms, next_room_number)     #3
        rooms[room_number][1] = next_room_number #4
    
    return next_room_number

최종 결과

import sys
sys.setrecursionlimit(200000)

def get_next_room_number(rooms, room_number):
    is_occupancy, next_room_number = rooms.get(room_number, [False, room_number])

    if not is_occupancy:
        return room_number
    else:
        next_room_number = get_next_room_number(rooms, next_room_number)     #다음 방 번호
        rooms[room_number][1] = next_room_number
    
    return next_room_number

def solution(k, request_room_numbers):
    answer = []
    
    rooms = {}  #점유, 다음 방번호
    max_room_num = -1
    for request_room_number in request_room_numbers:
        max_room_num = max(max_room_num, request_room_number)
        rooms[request_room_number] = [False, request_room_number + 1]


    for request_room_number in request_room_numbers:
        occupancy, next_room_number = rooms[request_room_number]

        if not occupancy:
            rooms[request_room_number][0] = True
            answer.append(request_room_number)
        else:
            cand_number = get_next_room_number(rooms, next_room_number)
            rooms[cand_number] = [True, cand_number + 1]
            answer.append(cand_number)

    return answer


if __name__ == "__main__":
    k = 10
    room_number = [1,3,4,1,3,1] 
    result = [1,3,4,2,5,6]

    print(solution(k, room_number))

후기

오랜만에 유파 문제를 풀어봤다. 다행히도 머릿속에서 남아있었고 블로그 글을 쓰면서 다시 한번 유파를 복습해 봤다. 그리고 유파의 연산은 O(1)은 아닐 것이다.