외벽 점검 파이썬

1. 순열을 이용하여 완전탐색

from itertools import permutations
from bisect import bisect_right

def solution(n, weak, dist):
    l = len(weak)
    weak_line = weak + [w+n for w in weak]
    answer = []
    for friends in permutations(dist):
        for i in range(l):
            cnt = 0
            position = weak[i]
            for friend in friends:
                cnt += 1
                position += friend
                if position < weak_line[i+l-1]:
                    position = weak_line[bisect_right(weak_line,position)]
                else:
                    answer.append(cnt)
                    break
                    
    return min(answer) if answer else -1

예를들어 n=12, weak = [1,5,6,10], dist = [1,2,3,4]일때, weak_line = [1,5,6,10,13,17,18,22]를 만든다.

그 후 permutations(dist)로 순열을 만든다. 친구를 한명씩 투입해 각 취약점을 검사한다.

현재 투입된 친구로 모든 취약점을 검사하지 못했다면, 현재 위치에서 가장 가까운 다음 취약점에서 친구를 한명 더 투입한다.(bisect_right 사용)

모든 취약점을 확인했다면, 검사에 투입된 친구의 수를 answer에 추가한다.

 

 

 

2. dist 내림차순 정렬 후 모든 취약점 검사

def solution(n, weak, dist):
    l = len(weak)
    weak_line = weak + [w + n for w in weak]
    dist.sort(reverse=True)
    repaired_list = [()]
    cnt = 0

    for d in dist:
        repairs = []
        cnt += 1

        for i in range(l):
            start = weak[i]
            repairs.append(set([w % n for w in weak_line[i:i + l] if start + d >= w]))

        can = set()
        for r in repairs:
            for x in repaired_list:
                new = r | set(x)
                if len(new) == l:
                    return cnt
                can.add(tuple(new))
        repaired_list = can
    return -1

마찬가지로 weak_line을 만들고, 탐색거리가 긴 친구부터 모든 취약점을 검사하고 set에 저장한다. 시간효율성이 훨씬 좋음