[Seop's의 코드풀이] 프로그래머스 호텔방 배정

 

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

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

 

문제요약

문제를 읽어보면 쉽게 이해할 수준의 문제이다.  

시간복잡도를 고려하지만 않는다면 방이 차있을 경우 1씩 더해가면서 확인하는 작업을 하면 정확성 테스트는 통과 할 수 있다.  

하지만 1씩 더하는 방법을 사용할 경우 효율성 테스트에서 시간초과가 발생한다.

즉 방이 차있을경우 일일이 확인하지 않고 빠르게 배정된 방번호보다 크면서 비어있는 방을 찾는것이 관건이다.  

 

문제풀이 IDEA

이번 문제의 주요 IDEA는 방이 비어 있는 방을 가리키는 것이다. 

주요 알고리즘은 다음과 같다.  

• 방 딕셔너리를 생성하고 다음과 같은 Key, Value 값을 가지도록 한다.  
  Key : 방번호, Value : 다음으로 비어있는 방
• 방이 비어있을 경우(방 딕셔너리에 Key 값이 없을 경우) 
  - 방 딕셔너리에 방 추가 (Key : 방번호, Value : 방번호 + 1)
• 방이 차있을경우(방 딕셔너리에 Key 값이 있을 경우)
  - 해당 방의 Value 값으로 이동하여 방이 비어있는지 체크! (또 차있다면 재귀적으로 계속 체크)
  - 비어있는 방을 찾은후 해당 방번호 + 1 값을 여태 거쳐온 방 Value 값으로 입력

위의 알고리즘을 적용하여 문제의 예시를 그림으로 표현하면 다음과 같다.  

예정된 방 번호 : [1,3,4,1,3,1]

표 윗줄 : Dict Key (이해를 돕기 위해 10개를 만들어 놓았지만 실제 문제에서는 빈 Dict로 시작해야 합니다.)

표 아랫줄: Dict Value

빨간색 : 현재 입력 사항

갈색 : 기존 값 변동 사항

 

전체코드

import sys
sys.setrecursionlimit(10**9)
class Hotel :
    def __init__(self, room_number) :
        self.room_number = room_number
        self.roomDict = dict()
        self.answer = []
    
    def findEmptyRoom(self, num) :
        if num not in self.roomDict :
            self.roomDict[num] = num + 1
            return num 
        else :
            newNum = self.findEmptyRoom(self.roomDict[num])
            self.roomDict[num] = newNum + 1
            return newNum
    
    def getAnswer(self) :
        for i in self.room_number :
            n = self.findEmptyRoom(i)
            self.answer.append(n)
        return self.answer


def solution(k, room_number):
    result = []
    h = Hotel(room_number)
    result = h.getAnswer()
    return result

 

질문 및 피드백은 언제나 감사드립니다.