[프로그래머스][KAKAO_인턴][2019] 호텔 방 배정

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)
def find(room, i):
    if i not in room:
        room[i] = i + 1
        return i
    occupied = find(room, room[i])
    room[i] = occupied + 1
    return occupied

def solution(k, room_number):
    answer = []
    room = defaultdict()
    for num in room_number:
        answer.append(find(room, num))

    return answer

• 유니온 파인드
  
  • 원하는 방 번호에 대해, 배정이 가능한 번호를 저장

 

다른 사람이 작성한 코드

import sys
sys.setrecursionlimit(10000000) # 설정해주지 않으면 재귀가 많이 일어나면서 런타임에러 등이 나타날 수 있다.

def findEmptyRoom(number, rooms): # 빈방을 찾는 함수
    if number not in rooms:        
        rooms[number] = number + 1
        return number
    
    empty = findEmptyRoom(rooms[number], rooms)
    rooms[number] = empty + 1
    return empty


def solution(k, room_number):
    answer = []
    rooms = dict() # 몇번 방이 비어있는지 체크하는 딕셔너리

    for number in room_number:
        emptyRoom = findEmptyRoom(number, rooms)
        answer.append(emptyRoom)
    
    return answer

• 계속 시간초과가 발생해서 위 코드를 참고했다

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

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

 

기억해야할 것

• 딕셔너리를 이용한 유니온 파인드
  
  • 신기했던 게, 리스트로 똑같이 구현했는데 시간초과다
  • 아무래도 k가 10^12일 경우 초기화에만 해당 크기 만큼의 시간이 필요해서 발생하는 듯 하다