[프로그래머스] 코딩테스트 연습 - 호텔 방 배정(Python)

코딩테스트 연습 - 호텔 방 배정 [2019 카카오 개발자 겨울 인턴십]

풀이

level 4의 문제였지만 천천히 생각해보면 어렵지 않게 풀 수 있는 문제였다고 생각됩니다.

하지만 저는 천천히 생각해서 어려운 길로 돌아갔습니다..ㅎㅎㅎ 

문제의 중점은 k의 값이 엄청크니까 겹치는 방이 있을 때 얼마나 효율적으로 다음 방을 찾느냐겠죠.

제가 생각했던 방식은 dictionary를 사용해서 dict [방 번호] = 다음 방 번호의 형식으로 저장하는 것이었습니다. 

풀이하는 과정에서 필요 이상으로 복잡하게 구현해서 코드가 길어졌지만 통과는 하더군요.

풀이 후에 다른 사람들의 풀이를 보며 제 코드에 불필요한 작업들이 많았구나를 느껴서 한 번 더 구현했습니다ㅎㅎ 

 

Code 1

from collections import defaultdict
def solution(k, room_number):
    answer = []
    rdict = defaultdict()   # [first, num]
    for num in room_number:
        if num in rdict:    # 찾아서 넣는 경우
            first = num
            while True:		# 배정 가능한 방을 저장한 num까지 반복
                if rdict[first][0] == False:
                    first = rdict[first][1]
                else:
                    break
            temp = rdict[first][1]
            if temp+1 in rdict and rdict[temp+1][0]==True:	# 배정할 방 다음 방이 배정되어 있는 경우
                rdict[temp] = [False, first]
                rdict[first][1] = rdict[temp+1][1]
                rdict[temp+1] = [False, first]
            else:				# 배정할 방 다음 방이 배정되어 있지 않은 경우
                rdict[temp] = [False, first]
                rdict[first][1] = temp+1
            room = temp
        else:               # 그냥 넣어도 되는 경우
            if num+1 in rdict:	# 배정할 방의 다음 방이 배정되어 있는 경우
                rdict[num] = [True, rdict[num+1][1]]
                rdict[num+1] = [False, num]
            else:				# 배정할 방의 다음 방이 배정되어 있지 않은 경우
                rdict[num] = [True, num+1]
            if num-1 in rdict:	# 배정할 방의 이전 방이 배정되어 있는 경우
                first = num-1
                while True:
                    if rdict[first][0] == False:
                        first = rdict[first][1]
                    else:
                        break
                rdict[first][1] = rdict[num][1]
                rdict[num] = [False, first]
            room = num
        answer.append(room)
    return answer

이어진 방들의 경우 가장 낮은 번호의 방이 배정 가능한 다음 방을 저장하고 나머지 방은 가장 낮은 번호의 방을 저장하는 방식입니다.

 

Code 2

from collections import defaultdict
def solution2(k, room_number):
    answer = []
    rdict = defaultdict()
    for num in room_number:
        idx = num
        visit = {idx}			# 배정 가능한 방을 찾기 까지의 방문기록
        while idx in rdict:		# idx가 dictionary에 없을 때 까지 반복
            idx = rdict[idx]
            visit.add(idx)
        for room in visit:		# 방문했던 방들에 다음으로 배정가능한 번호를 저장
            rdict[room] = idx+1
        answer.append(idx)
    return answer

각 방들마다 다음 방들을 저장하고 있고 dictionary에 저장되어 있지 않은, 즉 배정 가능한 방을 찾으면 dictionary에 추가하고 방문했던 방들의 다음 방을 갱신하는 방식입니다.

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호배정된 방 번호

1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

 

입출력 예

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]