2019 카카오 겨울 인턴십 코딩테스트 - 호텔 방 배정 건너기(python)

❓ 문제 - 2019 카카오 겨울 인턴십 코딩테스트 호텔 방 배정 문제 - python 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/64063)

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

 

📝 문제해결법

 

1. 아래 사이트를 참고하여 문제해결법을 공부하였다.

(https://velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level4-%ED%98%B8%ED%85%94-%EB%B0%A9-%EB%B0%B0%EC%A0%95-Python)

 

2. 일단 처음 푼 방법이 for문 하나씩 확인해주면서 호텔방에 사람이 묶었는지 남길 수 있는 딕셔너리를 만들면서 해당 호텔방 번호를 키로 삼는 딕셔너리가 존재한다면 다음 호텔방번호를 확인하면서 남아있는 호텔방을 찾는 방법으로 문제를 해결하였다. 하지만 이렇게 하면 k값은 1이상 10^12인 이하인 자연수이기때문에 정확성은 통과하지만 효율성은 통과하지 못하게 된다. O(N^2)임..

 

 

3. 효율적인 풀이를 위하여 딕셔너리와 재귀함수 O(nlogn)를 활용한다.

• 일단 find_emptyroom 함수를 통하여 빈방을 찾는다.
• find_emptyroom 함수에는 일단 해당 확인이 필요한 호텔방 번호의 키를 갖는 딕셔너리가 존재하지 않으면 value 값을 호텔방 번호에 +1 하여 딕셔너리를 생성하고 해당 호텔방 번호가 비었다고 판단하여 해당 호텔방 번호를 리턴한다. 즉, 확인하는 호텔방 번호 +1을 부모노드로 삼는다.
• 또한 해당 확인이 필요한 호텔방 번호의 키를 갖는 딕셔너리가 이미 존재한다면, 다음 호텔방이 비었는지 확인하기 위해서 재귀함수를 호출하며, 해당 확인이 필요한 호텔방 번호로 키값으로 두는 딕셔너리의 value값을 재귀함수의 매개변수로 넣는다. 즉, 재귀를 통해 찾아지는 빈방의 번호 + 1을 부모노드로 삼는다.
• 재귀함수 결과 빈방이 찾아지면 그 값을 반환하고, 해당 확인이 필요한 호텔방의 키값을 갖는 딕셔너리의 value 값을 빈방의 번호로 바꿔준다.
• 또한 새로 찾은 빈방의 번호를 find_empty 함의 반환값으로 두고 그 값을 answer에 append 한다.  

 

 

💻 소스코드 

import sys
sys.setrecursionlimit(10000000) # 재귀함수 호출 시 런타임 에러 방지 위해

def find_emptyroom(chk, room_dict):
    if chk not in room_dict.key(): # 빈방이라면
        room_dict[chk] = chk + 1 # 딕셔너리 생성
        return chk

    empty = find_emptyroom(room_dict[chk], room_dict) # 빈방이 아니라면 재귀함수 호출
    room_dict[chk] = empty + 1 # (배정된 방 + 1)을 부모노드로 변경
    return empty

def solution(k, room_number):
    room_dict = {}
    answer = []
    for i in room_number:
        room = find_emptyroom(i, room_dict)
        answer.append(room)

    return answer