[アルゴリズム]外壁のチェック

[問題]外壁のチェック
https://programmers.co.kr/learn/courses/30/lessons/60062
トラブルシューティングのヒント

完全探索問題は,ランダムにすべての友人をリストしたすべてのソート配列を用いて,友人のすべての状況をリストした個数を求める.

題は脆弱点が「円形」であることを示している.円形で並べられたデータは、長さを2倍に増やし、円形を1文字にすることができます.

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]

各友人のすべての状況をリストする数は、配列によって求められる.

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)

開始点はすべての脆弱点である可能性があるため、クエリ回数が最も高いのは脆弱点の数です.

脆弱な場所からリストされた友人(ex(3,5,7))の移動数が増加した位置(友人がチェックできる最後の位置).たとえば、脆弱点が1の場合、最初の友人の位置は4です.

次の友人の位置が4であれば、4を超える弱点に達すると友人に投入されます.

位のプロセスを繰り返した後、投入した友人を答えに保存します.

にリストされている友人(3,5,7)の開始の弱点を増やし、以上の過程を繰り返し、投入された友人を確認し続けます.

が最も少ない投入された友人が確定した場合、以下に示す友人リストを変更し、上記の手順(ex)3,7,5)

を繰り返す.

の答えが質問に投入された友人を上回った場合、-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)

注意:[シーケンスと組合せ-組合せ、配列]
https://programmers.co.kr/learn/courses/4008/lessons/12836