[알고리즘] 외벽 점검

[문제] 외벽 점검
https://programmers.co.kr/learn/courses/30/lessons/60062

문제해결 hint

1. 완전 탐색 문제로 모든 친구를 무작위로 나열하는 모든 순열 permutations 를 이용하여 친구를 나열하는 모든 경우의 수를 구한다.
2. 문제에서 취약 지점이 '원형'으로 구성되어 있다고 설명하였다. 원형으로 나열된 데이터는 길이를 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]

3. 각 친구를 나열하는 모든 경우의 수는 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)

4. 시작 지점은 모든 취약 지점이 될 수 있으므로 최상위 for문의 횟수는 취약지점의 개수이다.
5. 취약지점으로부터 나열된 친구들(ex (3,5,7))가 이동하는 수만큼 position(친구가 점검할 수 있는 마지막 위치)를 늘려나간다. 예를들어 취약지점이 1이라면 첫번째 친구의 position은 4가 된다.
6. 다음 첫번째 친구의 position이 4라면, 4를 초과하는 취약지점에 도착할 경우 친구를 투입한다.
7. 위 과정을 반복한 후에 투입된 친구를 answer에 저장한다.
8. 나열된 친구들(3,5,7)의 시작 취약 지점을 늘리고 위 과정을 반복하여 투입된 친구를 계속해서 확인한다.
9. 최소 투입 친구가 확인되면 다음으로 나열된 친구 목록을 변경하고 위 과정을 반복한다(ex) 3,7,5)
10. 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