오랜만에 알고리즘 풀이 포스팅을 올리네요.
이번 문제는 2019 카카오 인턴십 문제 중 하나인 Lv.4 호텔 방 배정 입니다.
Level 4 치고는 간단한 지문이었지만 왠지 시간 초과가 발목을 잡을 것 같다는 느낌이 들었습니다.
문제 자체는 해시 테이블에서 해시 충돌을 해결하는 방법 중 선형 탐사와 유사한 방법으로 손님들의 방을 배정해주는 문제입니다.
맨 먼저 떠오를 법한 방법으로, 순차적으로 방을 배정하되 충돌이 발생하는 경우 다음 빈 방이 생길 때까지 찾다가 배정해주는 방식으로 했습니다.
그러나 이 경우 한 방에 지속적으로 손님이 들어가는 케이스에 O(n^2)이 되므로 안되리라 생각했고, 역시나 시간 초과가 떴습니다.
어떻게 하면 시간을 줄일 수 있을까? 고민하다가 운영체제의 페이징에서 사용하는 버퍼 캐시와 같은 느낌으로 마지막으로 충돌이 발생한 지점에 다음 지점을 기록해주는 장치를 두면 어떨까? 하는 생각이 들었습니다.
우선, 방을 표현하기 위한 자료구조로 해시테이블을 만듭니다.
그리고, 손님을 순차적으로 받으면서 방이 빈 경우(딕셔너리에 방 번호에 해당하는 key가 없는 경우) 충돌 시 배정해줄 바로 다음 방 번호를 저장합니다.
ex) 1번 방에 손님이 들어가면 딕셔너리에는 rooms[1] = 2 로 저장
rooms = {}
for num in room_number:
if rooms.get(num) is None:
rooms[num] = num+1핵심이 되는 충돌처리는 다음과 같은 아이디어로 생각했습니다.
1) 충돌이 발생한 경우 우선 해당 방번호에 저장돼있던 다음 방으로 가본다.
2) 해당 방이 빈 경우 해당 방에 손님을 배정한다.
3) 충돌이 발생한 경우에는 또 그 방에 기록된 다음 방을 방문해본다
4) 배정이 가능할 때까지 반복한다. 가능한 이유는, 방 배정이 불가능한 경우는 없기 때문이다.
5) 마지막으로, 방문했던 모든 방은 맨 먼저 충돌이 일어난 방을 가리키게 만들고, 첫 방은 배정된 방의 다음 번호를 가리킨다.
성공한 이유는 개인적으로 5번인 것 같습니다. 처음에는 방문했던 방을 모두 리스트에 담았다가 하나씩 꺼내면서 최종 방번호로 업데이트했는데, 그냥 모두 첫 방을 가리키게 만들고 첫 방만 업데이트하는 방식을 선택했습니다. ~
(알고보니 다른 풀이 중 이렇게 해도 통과하는 풀이가 있더군요, 처음엔 방을 리스트로 만들어서 통과가 안됐나봅니다.. 다만 통과 시간으로 이 풀이가 조금 더 빨라서 마냥 헛수고를 한 건 아니구나 하는 생각이 듭니다.. )
ex) 현재 방 상황 : 1번 방, 2번 방, 3번 방, 4번 방(충돌이 한번도 없었다고 가정)
1번을 원하는 손님 입장 : 1번이 가리키는 2번 방으로 이동 ->
2번은 이미 선점되었으므로 2번이 가리키는 3번 방으로 이동 ->
3번도 이미 선점되었으므로 3번이 가리키는 4번 방으로 이동 ->
4번도 이미 선점되었으므로 4번이 가리키는 5번 방으로 이동 ->
5번 방은 비었으므로 5번 방에 손님을 배정하고 2,3,4,5번 방은 방문 당시 1번 방을 가리키게 됨.
1번은 5번의 다음 방인 6번 방을 가리킨다.
코드로 보면 다음과 같습니다.
# 방 번호 충돌 발생 시
else:
start = num # 충돌이 발생한 첫 방 번호 저장
next_num = rooms[num] # 가리키는 다음 방으로 이동
while rooms.get(next_num) is not None: # 충돌이 일어나는 방들이 가리킨 다음 방이 빌 때까지 반복
temp = next_num
next_num = rooms[next_num] # 충돌이 일어났으므로 다음 방을 탐색
rooms[temp] = start # 탐색한 모든 방을 첫 방을 가리키게 만듦
rooms[next_num] = start
rooms[start] = next_num + 1 # 첫 방은 손님이 들어간 다음 방을 가리키게 됨
num = next_num
answer.append(num)
더 좋은 풀이를 다른 분들의 풀이를 보며 고민해봐야겠습니다.
최악의 케이스인 모두 충돌이 발생해도 이 풀이를 이용하면 빈 방을 찾아가는 시간을 줄일 수 있어 O(n)에 근접하는 것 같습니다.
전체 코드는 다음과 같습니다.
def solution(k, room_number):
answer = []
rooms = {}
for num in room_number:
if rooms.get(num) is None:
rooms[num] = num+1
# 방 번호 충돌 발생 시
else:
start = num # 충돌이 발생한 첫 방 번호 저장
next_num = rooms[num] # 가리키는 다음 방으로 이동
while rooms.get(next_num) is not None: # 충돌이 일어나는 방들이 가리킨 다음 방이 빌 때까지 반복
temp = next_num
next_num = rooms[next_num] # 충돌이 일어났으므로 다음 방을 탐색
rooms[temp] = start # 탐색한 모든 방을 첫 방을 가리키게 만듦
rooms[next_num] = start
rooms[start] = next_num + 1 # 첫 방은 손님이 들어간 다음 방을 가리키게 됨
num = next_num
answer.append(num)
return answer시간 복잡도 : O(n) , n: 손님의 수
