[programmers] 프로그래머스 호텔 방 배정(Python)

(주)그렙

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

(Python)

(글쓴날 : 2020.05.18)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 호텔 방 배정

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64063

코딩테스트 연습 - 호텔 방 배정

---

2) 풀이 과정

* 시간 복잡도 : O(α(n), α : 아커만 함수)

 

방이 총 k개인 호텔에 고객들을 배정할 때, 만약 고객이 원하는 방이 비어있을 시 그 방을 배정하고, 비어있지 않다면 고객이 원하는 방보다 번호가 크면서 가장 작은 번호의 남은 방을 배정하여, 각 고객에게 배정되는 방 번호를 순서대로 배열에 저장하는 문제입니다.

 

저의 경우, 유니온 파인드를 적용하였고, Python을 사용했습니다.

먼저 배정된 방을 기록할 dictionary를 선언하였고, 그 후 고객들이 원하는 방을 탐색하여 해당 방이 비어있는지 find() 함수로 확인했습니다.

만약, 비어있다면 dictionary의 key에 방 번호, value에 key + 1을 저장하여 후에 이미 배정된 방을 원하는 고객이 있을 시 바로 해당 방의 다음방을 배정할 수 있도록 구현하였고, 비어있지 않다면 해당 방의 value 값을 다시 재귀 호출하여 비어있는 방을 찾아 문제를 해결했습니다.

 

중요했던 부분은 find() 함수에서 재귀 호출 시마다 경로 압축 최적화를 한다는 것인데 자식 노드들의 값을 모두 루트 노드로 바꿈으로써 탐색에 걸리는 시간 복잡도 효율이 높아져 효율성 테스트를 통과할 수 있었습니다.

또한, Python의 경우 sys.setrecursionlimit() 함수로 재귀 호출 깊이의 제한을 조절해 주셔야 런타임 에러가 발생하지 않습니다.

---

3) 코드

 

* Python 코드

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
 
 
def find(room, reservedRooms):
    if room not in reservedRooms:
        reservedRooms[room] = room + 1
        return room
    
    reservedRooms[room] = find(reservedRooms[room], reservedRooms)
    return reservedRooms[room]
 
 
def solution(k, room_number):
    answer = []
    reservedRooms = dict()
    
    for room in room_number:
        remainedRoom = find(room, reservedRooms)
        answer.append(remainedRoom)
        
    return answer

---