프로그래머스 - 외벽점검 (level3)

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/60062

문제 설명

n 길이의 외벽이 있고, 최약 지점 위치가 담긴 배열이 있다.
친구들마다 1시간동안 이동할 수 있는 거리가 다르다.
취약 지점을 모두 점검하기 위해 보내야 하는 친구 수의 최소값을 구하자.

풀이

1. 친구 수의 최소값을 구하는 문제기 때문에 먼저 이동 거리가 긴 순으로 보내는 것이 이득일까?
2. 앞의 최약지점을 시작으로 최대한 많은 최약 지점을 커버할 수 있는 친구를 찾아야 할 것이고, 그 친구들 중에서는 최소 이동 거리를 보내는 것이 이득이.

-> 최약지점을 앞에서부터 순서대로 확인하고, 내림차순 정렬한 이동 거리를 앞에서부터 확인해서 커버하는 최약지점 개수가 바뀌는 위치를 찾자. 그 위치 -1의 친구를 내보내는 방법으로 구현하기

def solution(n, weak, dist):
    dist.sort(reverse=True)
    count = 0
    while dist:
        if len(weak) == 0:
            return count
        check_range = weak[0] + dist[0]
        for w in weak:
            if w > check_range:
                tmp_fix = weak.index(w)-1
        
        for d in dist:
            check_range = weak[0] + d
            for w in weak:
                if w > check_range:
                    fix = weak.index(w)-1
                    break
            if fix != tmp_fix:
                send = dist.index(d)-1
                count += 1
                break
        dist = dist[send+1:]
        weak = weak[fix+1:]
    return -1

처음 작성한 풀이는 경우에 따라 실패했다. 다시 문제를 살펴보니 원형 외벽이라는 점을 간과하고 있었고, 중간부터 시작할 수 있고 앞으로도 돌 수 있다는 걸 깨달았다.
그렇다면 이제 어떻게 풀어야 할까?

투입할 친구 순서+수, 점검 시작 위치 정하고ㅡ 투입할 친구를 거리가 가장 먼 친구들 i명 뽑아서 순열을 만들어보자.
ex) 친구 = [1,2,3,4]일 때 1명만 탐색가는 경우 [4]로 안되면 [1],[2],[3]은 할 필요 없다.
i번 친구 투입
남아있는 지점 중 첫번째 지점 ~ 첫번째 지점 + 친구 이동거리
-> 위 범위에 있는 취약 지점은 i번 친구가 해결

코드

# n 길이의 외벽이 있고, 최약 지점 위치가 담긴 배열이 있다.
# 친구들마다 1시간동안 이동할 수 있는 거리가 다르다.
# 취약 지점을 모두 점검하기 위해 보내야 하는 친구 수의 최소값을 구하자.

from itertools import permutations

def solution(n, weak, dist):
    dist.sort(reverse=True)
    len_weak = len(weak)
    weak = weak + [num+n for num in weak] 
    
    for i in range(1,len(dist)+1):
        for ff in permutations(dist[:i]):
            for idx in range(len_weak):
                friends = list(ff[:])
                new_weak = weak[idx:idx+len_weak]
                while friends and new_weak:
                    f = friends.pop(0)
                    w = new_weak.pop(0)
                    current = f+w

                    while new_weak and new_weak[0] <= current:
                        new_weak.pop(0)
                
                if len(new_weak) == 0:
                    return i
    return -1
            

n = 12
weak = [1, 3, 4, 9, 10]
dist = [3, 5, 7]

print(solution(n, weak, dist))