[Python/파이썬 프로그래머스] 호텔 방 배정

programmers.co.kr/learn/courses/30/lessons/64063

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

풀이

1) 내가 푼 풀이 (실패)

덱과 check리스트를 이용해서

False값이면 통과

True면 다시 넣어서 따져줬는데

정확성은 통과하구 효율성은 통과하지 못했따.

딕셔너리를 써야할 느낌은 왔는데 어떻게 구현해야할지 감이 안옴...

from collections import deque
k=10
room_number=[1,3,4,1,3,1]


answer = []
check=[False]*(k+1)
queue=deque()
for _ in range(len(room_number)):
    queue.appendleft(room_number.pop())

while queue:
    room=queue.popleft()
    
    if check[room]==False:
        answer.append(room)
        check[room]=True
    else:
        queue.appendleft(room+1)

print(answer)

 

2) 정석풀이

tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

결국 답지를 참고했는데

풀이는 딕셔너리를 사용하여

key 값에는 호텔 방 value 값에는 다음 빈 방 값을 넣어서

순차적으로 탐색을 하지 않고 다음 빈 방을 빠르게 찾고,

만약 빈 방이 차게 된다면 방문한 부모 노드 값들도 변화시켜주는 방법

import sys
sys.setrecursionlimit(10000) # 재귀 리미트- 설정할 시 범위까지만 재귀 돈다

def find(chk,rooms):
    if chk not in rooms:
        rooms[chk]=chk+1
        return chk

    empty=find(rooms[chk],rooms)
    # 빈방이 나오기 전 방문했던 부모 노드 바꿔줌
    rooms[chk]=empty+1
    return empty

def solution(k,room_number):
    answer=[]
    # 해당 value는 다음 빈 방 번호 값
    rooms=dict()

    for i in room_number:
        chk_in=find(i,rooms)
        answer.append(chk_in)

    return answer

.

.

재귀가 나오면 헷갈리는거 같다...

이해하는데도 꽤 시간이 걸린 문제..

딕셔너리를 알맞게 사용하면 시간 단축에 효율적인 것을 숙지하자!!