[프로그래머스] 외벽 점검 in python

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

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

 

유형 : 구현 , 완전 탐색 

 dist의 길이가 8로, 8! 을 해도 10만을 넘지 않는다. 따라서 완전 탐색으로 풀어도 가능하다. 

1. 원을 리스트로 바꿔서 생각하기 

예시 2의 취약 지점을 원에 표현하면 다음과 같다. 

원형일 경우 0 지점을 넘어갈때 계산이 불편하므로, 이를 일직선 상에 놓는다. 각각의 지점에 n 만큼을 더해주면 한바퀴 돈 다음의 position을 구할 수 있다.

그렇게 되면 [1, 3, 4, 9, 10, 13, 15, 16, 21, 22] 이 일직선 상에 놓인다고 생각할 수 있다. 

 

2. 완전탐색을 위해서, itertools 라이브러리의 permutations로 dist의 모든 순열 구하기

dist 의 원소들을 나열하는 모든 경우를 permutations() 함수를 통해 구한다.

dist = [3, 5, 7]의 경우 

[3, 5, 7] [3, 7, 5], [5, 3, 7], [5, 7, 3], [7, 3, 5], [7, 5, 3] (== 3! ) 총 6개의 경우가 나오는데 이를 list로 묶어서 완전 탐색에 이용했다.

 

3. 현재 위치를 구한다. 취약 지점이 있는 지점을 기준으로, 친구가 갈 수 있는 거리를 더한다,

그리고 그 때의 위치가 weak[i] 보다 큰지 작은지 비교해서, 작다면 친구를 추가하고 현재위치를 갱신한다.

 

전체 코드 

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak) # 취약 지점의 길이 
    for i in range(length):
        weak.append(weak[i] + n) # 2배로 길이를 늘려서 선형으로 나열하기 
    
    # 친구들 정렬 순서 모든 경우를 구하기
    answer = len(dist)+1 
    
    for start in range(length): # weak point들 중에서 시작점 정하기
        for case in list(permutations(dist, len(dist))):
            count = 1
            position = weak[start] + case[count-1]
            for i in range(start, start + length): # 취약지점 시작점 부터 모두 확인하기 이미 취약 지점을 2배로 늘려서 가능함
                if position < weak[i]:
                    count += 1
                    if count > len(dist): # 더이상 친구가 없으면 탐색 실패 
                        break
                    position = weak[i] + case[count-1]
        answer = min(answer, count)
  
    if answer > len(dist):
        return -1
    return answer