Programmers. 외벽 점검

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 외벽 점검

문제 풀이

그리디인줄 알았는데 브루트포스였다. 친구의 거리를 정렬해서 도입해도 특정 친구가 반드시 특정 지점에 가야함 정답이 성립하는 케이스가 존재하기 때문으로 보인다. 주어진 모든 친구의 투입 경우의 수를 순열로 생성해 대입해야 한다. 그리고 원형 구조는 길이를 정확히 두 배로 늘려서 해결할 수 있음을 이 문제를 통해 알 수 있었다.

길이를 두 배로 늘렸어도 탐색 시작 좌표는 기존 배열 내로 유지해야 하므로 늘리기 전에 전체 취약점 개수를 저장해야 한다. 매 출발 포인터에 대해 취약점 배열을 생성하고 모든 친구 투입 순서 경우에 대해 투입 시 카운트를 1 올리고 친구의 좌표를 0에서 1씩 더해 현재 친구의 탐색 지점과 탐색 가능 거리를 설정한다. 그리고 모든 취약점 포인트에 대해 현재 친구의 탐색 거리와 비교하여 탐색 거리가 만료되면 친구를 교체해되 전부 투입했으면 break한다.

• 반시계 회전은 시계 방향에서 더 진행함을 의미하므로 외벽 길이만큼 더해서 뒤에 붙인다.
• 모든 친구 투입 경우의 수를 순열로 생성한다.
• 모든 출발 지점에 대해 순회를 하는 반복문을 정의한다.
• 시작 지점에 따른 취약점 거리 배열을 정의한다.
• 친구 순서에 대해 순회하는 반복문 정의한다.
• 현재 친구가 순회 가능한 거리보다 크다면 친구를 교체한다.
• 순회가 끝나면 투입된 친구 개수를 업데이트한다.

python 코드

from itertools import permutations
def solution(n, weak, dist):
    weak_len = len(weak)
    for i in range(weak_len):
        weak.append(weak[i] + n)
    dist_permu_set = list(permutations(dist, len(dist)))
    answer = len(dist) + 1
    for i in range(weak_len):
        start = [weak[i + j] for j in range(weak_len)]
        for dist_p in dist_permu_set:
            result = 1
            dist_c = 0
            dist_v = start[0] + dist_p[dist_c]
            for k in range(weak_len):
                if dist_v < start[k]:
                    result += 1
                    dist_c += 1
                    if result > len(dist_p):
                        break
                    dist_v = start[k] + dist_p[dist_c]
            answer = min(answer, result)
    if answer > len(dist):
        return -1
    else:
        return answer