[카카오] 프로그래머스: 60062번

-문제: https://programmers.co.kr/learn/courses/30/lessons/60062?language=python3 

코딩테스트 연습 - 외벽 점검

 

weak의 위치가 원형으로 이루어져 있어서 어떻게 풀어야 할지 몰랐던 문제다. 

친구의 수와 취약점들의 갯수가 많지 않으므로 완전 탐색을 통해서 답을 낼 수 있다. (주어진 조건들의 갯수 확인하기)

원형으로 주어지면 각 리스트의 값에 n을 더해 리스트의 길이를 늘려준다. 

거기서 친구별로 갈 수 있는 길이만큼 탐색을 하는 방식으로 하면 된다. 

 

from itertools import permutations

def solution(n, weak, dist):
    
    length= len(weak)
    for i in range(length):
        weak.append(weak[i]+n)
    
    #친구수 +1, min사용 & 친구 전체를 투입해야 할 수 있으니까
    answer = len(dist)+1
    
    for start in range(length):#각각의 weak 포인트들로부터 시작하기 
        for friends in list(permutations(dist,len(dist))):
            cnt=1            
            #시작하는 취약점 + 친구가 1시간에 이동할 수 있는 거리(해당 친구가 점검할 수 있는 마지막 위치)
            position= weak[start]+friends[cnt-1] 
            #시작점부터 모든 취약점을 확인
            for index in range(start,start+length):
                if position < weak[index]:#해당친구 점검이 끝나도 취약지점이 있을때
                    cnt+=1 #친구 추가
                    if cnt>len(dist):
                        break 
                    position = weak[index]+friends[cnt-1]
            answer= min(answer,cnt)
            
    if answer>len(dist):
        return -1
    return answer