[Python] 프로그래머스. 2020 카카오 recruit - 외벽 점검 (Level 3)

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

코딩테스트 연습 - 외벽 점검 | 프로그래머스

 

어디서부터 어떻게 손대야 할지 감도 안 와서 어려웠던 문제.

검색해서 알아봐도 풀이방법이 참 다양하다. DFS, Brute Force, DP 등등

 

최대한 내가 이해한 방향으로 풀어보자면

 

1. 시계 - 반시계 문제는 배열을 두 배 늘려서 해결한다.

예컨대 위 사례에서 "4에서 출발해 반시계 방향으로 7만큼 돌면 9에 도착한다"는 건,
"9에서 출발해 시계 방향으로 7만큼 돌면 4에 도착한다" 와 같은 말이다.

문제에서 외벽 길이는 12였으므로, 9에서 출발해 4에 도착한다는 건, 9에서 7만큼 이동한 16이 4와 같다는 뜻이다.

 

따라서 위 사례의 경우 [1,3,4,8,9,10]에 "각 원소 + 외벽길이"를 붙여준다.

그러면 [1,3,4,8,9,10, 12 + 1, 12 + 3, 12 + 4, 12 + 8, 12 + 9, 12+ 10]이 되는데,

외벽 검사 출발할 지점을 1, 3, 4, 8, 9, 10 중 하나로 선택하면 시계 / 반시계 문제는 해결된다.

 

2. 두 배 늘린 배열에서, 외벽 검사를 시작할 지점부터 len(weak) 만큼의 원소를 탐색해야 한다.

 

3. dist에 있는 친구 배열도 모든 경우의 수를 따져야 한다. permutations로 모든 경우의 수를 만들어준다.

 

4. 탐색한다.

 

	from itertools import permutations
	def solution(n, weak, dist):
	# 1. 시계 / 반시계 문제 해결하기
	weak_length = len(weak)
	for i in range(weak_length):
	weak.append(weak[i] + n)
	# 4에서 반시계방향 = 9에서 시계방향.
	# 즉 길이를 두 배 늘려놓으면 굳이 방향 고민할 필요 없다
	# 투입할 수 있는 친구의 최댓값.
	# 점검 불가능한 경우를 상정해서 len(dist) + 1
	answer = len(dist) + 1
	for i in range(weak_length):
	# 2. 어디서부터 벽 점검을 시작할 것인지 결정
	start_point = [weak[j] for j in range(i, i + weak_length)]
	# 3. 벽 점검에 투입할 친구의 순서 정하기
	candidates = permutations(dist, len(dist))
	# 4. 탐색
	for order in candidates:
	# 순서대로 출발.
	friend_idx, friend_count = 0, 1
	# 친구가 확인할 수 있는 최대 거리
	possible_check_length = start_point[0] + order[friend_idx]
	for idx in range(weak_length):
	# 확인할 수 있는 최대 거리를 넘어설 경우
	if start_point[idx] > possible_check_length:
	# 다음 친구 투입
	friend_count += 1
	# 더 이상 투입할 친구가 없는 경우 break
	if friend_count > len(order):
	break
	# 다음 친구 투입, 친구가 확인할 수 있는 최대 거리 업데이트
	friend_idx += 1
	possible_check_length = order[friend_idx] + start_point[idx]
	# 투입할 친구 최솟값 업데이트
	answer = min(answer, friend_count)
	if answer > len(dist):
	return -1
	return answer

view raw [프로그래머스] 외벽 점검.py hosted with ❤ by GitHub