[Python] 프로그래머스. 2019 카카오 겨울 인턴 recruit - 호텔 방 배정 (Level 4)

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

프로그래머스

 

 

union find 형태의 문제. 백준 10775 공항 문제를 참고하면 좋다.

이런 형태의 문제는 이전에 풀어 봤다. k가 10^12나 되는 큰 크기이기 때문에, 저 숫자만큼의 배열이나 dictionary를 선언하지 않는 게 시간초과를 막는 핵심.

 

[Python] 백준 10775. 공항

 

그리고, 내 풀이에서는 recursionLimit 제한을 높이지 않으면 효율성 테스트에서 한 문제가 런타임 에러 뜬다.

19년 12월 코딩테스트를 볼 때 디버깅하느라 시간 많이 잡아먹었던 원인 중 하나였다.

 

 

	import sys
	sys.setrecursionlimit(1500)
	# 방을 찾는 함수
	def find_empty_room(x, rooms):
	# 현재 방넘버 x에 아무도 배정되지 않은 경우
	if x not in rooms:
	# 현재 방넘버 기준, 다음으로 빈 방 좌표를 저장한다.
	rooms[x] = x + 1
	# 현재 방넘버 x를 반환한다.
	return x
	# 아무도 배정받지 않은 방이 나올 때까지 함수를 시행한다.
	p = find_empty_room(rooms[x], rooms)
	rooms[x] = p + 1
	return p
	def solution(k, room_number):
	# 해당 번호 기준, 그 번호보다 값이 크면서 빈 방의 좌표를 저장하는 dict
	rooms = dict()
	answer = []
	for each_room in room_number:
	empty_room = find_empty_room(each_room, rooms)
	answer.append(empty_room)
	return answer

view raw [프로그래머스] 호텔 방 배정.py hosted with ❤ by GitHub