외벽 점검

https://school.programmers.co.kr/learn/courses/30/lessons/60062

결국 풀지 못한 구현문제다.

import copy

#좌표를 벗어났을 때의 반례가 있는거같다. 아니면 논리상의 허점이 있거나. 재귀로 한다음에 결과 없으면 -1리턴하는걸로?
#구한 weak_temp나 reverse를 다시 함수에 넣어서 검사

def solution(n, weak, dist): #n은 외벽 길이, weak는 취약점, dist는 친구별 이동가능거리
    answer = 0
    #반시계/시계방향 둘 다 신경써야됨
    #친구들은 정수좌표에서만 출발하지는 않는듯.
    #각 dist원소별로 가장 긴 것부터 경우의수 전부 체크?
    total = 0 #고친 weakpoint 총 개수
    dist = dist
    
    def iscorrect(dist_points, weak_points):
        if total == len(weak):
            return True
        if len(dist_points) == 0:
            return False
        
        count = [] #각 weak point별 dist의 점검가능 개수
        friend_dist = dist.pop(-1) #가장 큰 이동거리 친구 뽑기
        for weakpoint in weak:
            count_fixed = 0 #점검한 weak포인트 수
            weak_temp = copy.deepcopy(weak)
            for k in range(0, friend_dist+1):
                position = (weakpoint + k) % n #시계방향
                if position in weak_temp:
                    weak_temp.remove(position)
                    count_fixed += 1
            count.append((count_fixed, weakpoint, 1)) #점검 weakpoint개수와 그때의 출발좌표 저장
            
            count_fixed_reverse = 0
            weak_temp_reverse = copy.deepcopy(weak)
            for k in range(0, friend_dist+1):
                position = (n + (weakpoint - k)) % n #반시계방향
                if position in weak_temp:
                    weak_temp_reverse.remove(position)
                    count_fixed_reverse += 1
            count.append((count_fixed_reverse, weakpoint, -1)) #점검 weakpoint개수와 그때의 출발좌표 저장
        #시계방향/반시계방향으로 돌려서 고친 point수 중 가장 큰 것의 개수와 좌표를 뽑음
        count.sort(key = lambda x: x[0], reverse = True)
        max_count, max_point, clockwise = count[0]
        if clockwise == 1:
            weak = weak_temp
        else:
            weak = weak_temp_reverse
        total += max_count
        answer += 1 #친구수 더하기
        
        
        
        
    
    
    while len(dist) > 0:
        
        if total == len(weak): #모든 weak point를 고치면 그때의 친구수 리턴
            return answer

    return -1

solution(12, [1, 3, 4, 9, 10], [3, 5])

생각을 해보니 그냥 친구를 배치하는 경우의 수를 전부 고려해도 40000언저리가 되기 때문에 순열을 사용하면 훨씬 쉽게 풀리는 문제였다.

문제를 풀기 전에 문제 조건을 잘 살펴보고 어떻게 풀지에 대한 전략을 먼저 세우는게 중요하다고 느꼈다. 그래도 반시계 방향과 시계 방향을 살펴보는 것을 직접 짜보았다는 점이 의의가 있지 않을까 싶다. 나중에 다시 풀어봐야겠다.