[파이썬 | 2019 카카오 코딩테스트 | 문제 4] 호텔 방 배정

문제 4

• 문제4 풀러 가기

프로그래머스

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

입출력 예

kroom_numberresult

10

[1,3,4,1,3,1]

[1,3,4,2,5,6]

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다. 네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번…] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

 

풀이

만약 이용자가 원하는 방이 아직 있다면, 바로 배정을하고 그 방의 dictation값을 그 방 다음 값으로 설정한다.

만약 이용자가 원하는 방이 이미 있다면, (dictation.get(원하는 방)이 None이 아니라면), 배정할 수 있는 방인 dict[원하는 방]값이 None이 나올때 까지 계속 계속 원하는 방을 갱신하면서 탐색한다.

 

그리고 나서 결국 배정할 수 있는 방이나오면, 지금까지 거쳐왔던 방들을 모드 배정할 수 있는 방 + 1로 갱신한다.

 

	# [파이썬 | 2019 카카오 인턴쉽] 호텔 방 배정
	import sys
	sys.setrecursionlimit(10000)
	def solution(k, room_number):
	def findAvailRoom(each_room):
	temp = []
	while check.get(each_room) is not None:
	temp.append(each_room)
	each_room = check[each_room]
	#print(temp)
	for t in temp:
	check[t] = each_room + 1
	check[each_room] = each_room + 1
	return each_room
	answer = []
	check = {}
	for each_room in room_number:
	answer.append(findAvailRoom(each_room))
	#print(answer)
	return answer
	# 테스트용 input output 정의
	# 10
	# 1 3 4 1 3 1
	k = int(input())
	room_number = list(map(int, input().split()))
	solution(k, room_number)

view raw KAKAO2019W4.py hosted with ❤ by GitHub