[알고리즘] 외벽 점검
[문제] 외벽 점검
https://programmers.co.kr/learn/courses/30/lessons/60062
문제해결 hint
- 완전 탐색 문제로 모든 친구를 무작위로 나열하는 모든 순열 permutations 를 이용하여 친구를 나열하는 모든 경우의 수를 구한다.
- 문제에서 취약 지점이 '원형'으로 구성되어 있다고 설명하였다. 원형으로 나열된 데이터는 길이를 2배로 늘려서 원형을 일자 형태로 만들어주는 작업을 해준다.
weak = [1, 3, 4, 9, 10]
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
result
weak = [1, 3, 4, 9, 10, 13, 15, 16, 21, 22]
- 각 친구를 나열하는 모든 경우의 수는 permutations 를 통해 구한다.
for friends in list(permutations(dist, len(dist))):
print(friends)
result
(3, 5, 7)
(3, 7, 5)
(5, 3, 7)
(5, 7, 3)
(7, 3, 5)
(7, 5, 3)
- 시작 지점은 모든 취약 지점이 될 수 있으므로 최상위 for문의 횟수는 취약지점의 개수이다.
- 취약지점으로부터 나열된 친구들(ex (3,5,7))가 이동하는 수만큼 position(친구가 점검할 수 있는 마지막 위치)를 늘려나간다. 예를들어 취약지점이 1이라면 첫번째 친구의 position은 4가 된다.
- 다음 첫번째 친구의 position이 4라면, 4를 초과하는 취약지점에 도착할 경우 친구를 투입한다.
- 위 과정을 반복한 후에 투입된 친구를 answer에 저장한다.
- 나열된 친구들(3,5,7)의 시작 취약 지점을 늘리고 위 과정을 반복하여 투입된 친구를 계속해서 확인한다.
- 최소 투입 친구가 확인되면 다음으로 나열된 친구 목록을 변경하고 위 과정을 반복한다(ex) 3,7,5)
- answer가 문제에서 투입된 친구보다 넘었을 때에는 -1 을 리턴한다.
from itertools import permutations
n = 12
weak = [1, 3, 4, 9, 10]
dist = [3, 5, 7]
def solution(n, weak, dist):
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
# 투입할 친구 수 초기화
answer = len(dist) + 1
# 0부터 length - 1 까지의 위치(취약지점)를 각각 시작점으로 설정
for start in range(length):
for friends in list(permutations(dist, len(dist))):
# 투입할 친구의 수
count = 1
position = weak[start] + friends[count - 1]
# 시작지점부터 모든 취약지점을 확인
for index in range(start, start + length):
# 점검할 수 있는 위치를 벗어나는 경우
if position < weak[index]:
# 새로운 친구를 투입
count += 1
# 더 투입이 불가능하다면 종료
if count > len(dist):
break
position = weak[index] + friends[count - 1]
# 최소값 계산
answer = min(answer, count)
if answer > len(dist):
return -1
return answer
solution(n, weak, dist)
참고 [순열과 조합 - combinations, permutations]
https://programmers.co.kr/learn/courses/4008/lessons/12836
Author And Source
이 문제에 관하여([알고리즘] 외벽 점검), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yj-leee/알고리즘-외벽-점검저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)