[프로그래머스] 외벽 점검 - python

외벽 점검

문제

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

풀이

원형으로 나열된 데이터를 처리하는 경우 길이를 2배로 늘려서 일자 형태로 만들면 편하게 풀 수 있다.

1. Weak 배열을 2배로 늘려 일자 형태로 만든다.
2. 친구들의 순열을 구한다.
3. 각각의 경우에 취약한 지점을 모두 검사할 수 있는지 확인한다.
4. 0부터 len(weak)-1 까지 시작점을 바꿔보면서 확인한다.

만약 친구 배열보다 answer 값이 클 경우 -1을 리턴한다.

from itertools import permutations
def solution(n, weak, dist):
    length = len(weak)
    answer = len(dist) + 1
    weak.extend([w + n for w in weak])
    
    for start in range(length):
        for p in permutations(dist, len(dist)):
            cnt = 1
            max_range = weak[start] + p[cnt - 1]
            for i in range(start, start + length):
                if weak[i] > max_range:
                    cnt += 1
                    if cnt > len(dist):
                        break
                    max_range = weak[i] + p[cnt - 1]
            answer = min(answer, cnt)
    
    return answer if answer <= len(dist) else -1