[프로그래머스] 외벽 점검 / 2020 카카오 블라인드 채용 / python

첫번째 입출력 예를 보자.

원 형태이기 때문에 10을 수리하고 넘어가서 1을 수리해야 할 수도 있다.
위와 같은 경우가 있기 때문에 기존의 취약한 벽 리스트에 추가로 원 둘레만큼 더한 벽 번호들을 추가한다.(weak[i] + n을 쭉 추가함)

각 취약점 위치에서 시작하도록 for문을 돌린다. 0 ~ 3

• 현재 취약점에서 시작하는 취약점 순서 리스트를 만든다.

• i=0 : (1,5,6,10) -> i=1 : (5,6,10,13) -> i=2 : (6,10,13,17) -> i=3 : (10,13,17,18)

• 그리고 그 안에서 친구들이 갈 수 있는 거리 배열의 중복을 허용하지 않는 순열 리스트에서 for문을 돌린다.(모든 경우의 수를 찾기 위함)

  • 첫번째 친구가 갈 수 있는 거리를 정하고 친구 사용 카운트를 1 올린다.
  • 첫번째 친구가 갈 수 있는 거리를 넘어선 취약점에 도달했을 경우 그 두번째 친구를 선택하고 두번째 친구가 갈 수 있는 거리를 정한다.
  • 사용한 친구들의 수가 취약점의 수를 넘어섰거나 모든 취약점에 도달했을 경우 현재 사용한 친구들의 수가 정답보다 작다면 정답을 갱신한다.

위의 과정을 반복하다보면 정답을 구할 수 있다.

from itertools import permutations
import math


def solution(n, weak, dist):
    answer = math.inf
    weak_len = len(weak)

    for i in range(weak_len):
        weak.append(weak[i] + n)

    for i in range(weak_len):
        weak_order = [weak[j] for j in range(i, i + weak_len)]

        for dist_order in permutations(dist):
            friend_idx, friend_count = 0, 1
            possible_len = weak_order[0] + dist_order[friend_idx]

            for idx in range(weak_len):
                if weak_order[idx] <= possible_len:
                    continue

                friend_count += 1
                if friend_count > len(dist_order):
                    break

                friend_idx += 1
                possible_len = weak_order[idx] + dist_order[friend_idx]

            answer = min(answer, friend_count)

    return -1 if answer > len(dist) else answer