외벽 점검

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062?language=python3

코딩테스트 연습 - 외벽 점검

외벽의 길이가 n, 취약 지점의 위치가 weak, 각 친구가 이동할 수 있는 거리가 dist로 각각 주어집니다.

 

 

외벽이 원형으로 이루어졌기 때문에

길이가 100인 벽에서 지점 0과 지점 90까지의 최단 거리는 10입니다.

p1 >= p2일 때, dis = min(p1 - p2, p2 - p1 + n)이 성립합니다.

 

 

친구가 투입되는 순서가 정해졌다고 가정하면

각 취약점마다 차례대로 보내서 모든 취약점을 점검하기 위한 최소 인원을 구할 수 있습니다.

점검이 시작되는 지점을 하나씩 옮겨가면서 같은 과정을 반복하면

모든 경우에 대해 최소 인원을 갱신할 수 있습니다.

 

 

예시로 주어진 n = 12, weak = [1,5,6,10], dist = [1,2,3,4]의 경우에는

0번 친구가 1번 지점을 점검하고

1번 친구가 5,6번 지점을 점검,

2번 친구가 10번 지점을 점검하면

총 3명의 친구가 투입해서 점검을 완료할 수 있습니다.

 

0번 친구가 투입되는 최초 시작점을 옮기기 위해

weak를 수정하는 과정은 다음과 같습니다.

n = 12일때, 1번 지점은 13번 지점과 같습니다.

따라서 weak를 다음과 같이 수정할 수 있습니다.

weak = [5,6,10,13]

10번 지점은 -2번 지점과 같으므로

weak = [-2,1,5,6] 과 같이 수정할 수도 있습니다.

 

이제 같은 과정을 반복하면

0번 친구가 5번 지점을 점검하고

1번 친구가 6번 지점을 점검하고

2번 친구가 10,13번 지점을 점검합니다.

 

 

투입이 시작되는 지점을 바꿔가면서 위 과정을 n번 반복해 최소 인원을 갱신했다면

이번에는 투입되는 친구의 순서를 바꿔 전체 과정을 다시 반복합니다.

 

위에서는 친구가 반드시 [1,2,3,4] 순으로 투입된다고 가정했지만

모든 경우를 탐색하기 위해서 다른 순서로 투입되는 경우에 대해서도 모두 확인해야 합니다.

빠른 구현을 위해 itertools의 permutations 메서드를 사용했습니다.

dist의 순열 P를 구해 친구가 투입되는 순서에 대한 모든 경우를 확인합니다.

 

 

dist의 최대 길이가 8이므로 순열 P를 구하는 과정은 8!만큼 필요합니다.

또한 각 순열 요소에 대해 weak를 n번 수정하면서 최대 길이 15만큼 탐색하므로

모든 과정에 필요한 연산의 수는 최대 8! * 200 * 15 입니다.

 

이분 탐색을 활용하면 이 과정을 약간 더 빨라지도록 만들 수 있습니다.

weak는 항상 오름차순으로 정렬된 상태이기 때문에 이분 탐색을 바로 활용할 수 있습니다.

현재 투입된 위치를 w, 투입된 친구가 이동할 수 있는 거리를 d라고 하면

다음 친구가 투입되는 위치는 w+d보다 큰 값을 가지는 지점입니다.

 

 

외벽을 모두 점검할 수 있다면 투입되는 친구의 수는 반드시 len(dist)보다 작거나 같을 것이므로

answer는 len(dist) + 1로 초기화합니다.

모든 과정을 끝낸 뒤에 answer가 len(dist) + 1이라면 모든 외벽을 점검할 방법이 없는 것이므로

-1을 반환합니다.

 

from bisect import bisect_right
from itertools import permutations

def solution(n:int, weak:list, dist:list) -> int:
    P = list(permutations(dist, len(dist)))
    cnt = len(weak)

    answer = len(dist) + 1

    for p in P:
        for i in range(len(weak)):
            i_w, i_d = 0, 0
            while True:
                w, d = weak[i_w], p[i_d]
                i_w = bisect_right(weak, w + d)
                if i_w == len(weak):
                    answer = min(answer, i_d + 1)
                    break
                i_d += 1
                if i_d == len(p):
                    break
            
            temp = weak[-1] - n
            weak = [temp] + weak[:len(weak)-1]

    if answer == len(dist) + 1:
        return -1
    else:
        return answer