Solution

한참을 들여다보아도 아이디어가 전혀 떠오르지 않아 답안을 보고 문제를 풀었다.
입력 데이터의 범위가 작아서 완전탐색으로 모든 경우의 수를 체크해봐야겠다고는 생각했으나, 무엇을 기준으로 반복하고 어떻게 체크해야할지 감이 잡히지 않았다.

풀이의 전체적인 흐름은 다음과 같다

1. 원형으로 된 데이터를 일자로 만들기 위해 리스트의 길이를 2배로 늘림
2. 늘어나기 전 weak리스트를 출발점으로 하여 반복을 수행
3. 친구들을 배치할 순서를 permutation을 통해 모든 조합을 만들고 각 경우에 대해 검증
   3-1. 출발점에 배치된 친구가 최대로 점검할 수 있는 위치를 계산하여 position에 저장
   3-2. 출발점으로부터 한바퀴를 돌면서 점검하지 못한 곳이 나오면 그 자리에 다음 친구를 배치하고 현위치를 기준으로 position을 다시 계산
   3-3. 모든 친구를 배치했는데 점검하지 못한 곳이 나오면 다음 케이스로 넘어감
4. 배치된 친구수의 최솟값을 반환. 이때, 초기값과 같으면 -1(불가능)을 반환

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)

    answer = len(dist) + 1

    for start in range(length):
        for friends in list(permutations(dist, len(dist))):
            count = 1
            position = weak[start] + friends[count - 1]
            for index in range(start, start + length):
                if position < weak[index]:
                    count += 1
                    if count > len(dist):
                        break
                    position = weak[index] + friends[count - 1]
            answer = min(answer, count)

    if answer > len(dist):
        return -1

    return answer

결국 friends라는 순열을 만들고, 각 순열에 대해 weak를 탐색하면서 문제의 조건을 체크하면 문제를 해결할 수 있었다.

내가 생각했을 때, 이 풀이의 핵심은 아래와 같다.

1. 원형 탐색을 위해 리스트의 길이를 두배로 늘리고, 기존 리스트의 원소를 출발점으로 하여 start + length만큼 탐색을 하면 한바퀴를 탐색한 것과 동일한 효과가 나온다

# 원형 -> 선형
for i in range(length):
        weak.append(weak[i] + n)
...
# 탐색
for index in range(start, start + length):

2. 모든 경우의 수를 찾기 위해 순열 사용

from itertools import permutations
...
for friends in list(permutations(dist, len(dist))):

• 2020 KAKAO BLIND RECRUITMENT 외벽 점검
• 출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬