[프로그래머스/카카오] 외벽점검

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

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

 

1. 원형을 선형으로 생각해보자 , weak의 길이를 두배로 늘려서 선형으로 생각한다. 

2. 친구들을 배치해야한다. -> 파이썬에서는 순열 조합을 permutations 함수로 구현할 수 있다. 친구들을 배치하는 방법을 모두 구한다음에 완전탐색으로 필요한 친구의 최소 값을 구한다. dist의 길이가 1이상 8 이하이고 8! = 약 4만 정도이므로 완전탐색으로 풀어도 괜찮다.

 

우리가 점검할 레스토랑의 구조는 원형이다.

원형 구조에서 지점은 0 ~ n-1까지 n개이다. 이 weak의 길이를 두 배 늘려서 원형을 선 위에 놓고 생각할 수 있다.

입출력 예 2를 보면 

weak 는 [1, 3, 4, 9, 10] 이고 n 은 12 이다.

이를 두배로 늘려서 생각하면 1, 3, 5, 9, 10, (1+12), (3+12) ...

1, 3, 5, 9, 10, 13, 15, 21, 22 가 된다.그러면 우리가 원일 때 시계방향에서 0을 넘어가는 경우의 계산을 쉽게 생각할 수 있다. 

* 기억하자 구현에서는 길이나 크기를 늘려서 생각하면 좀 더 쉽게 접근 가능할 수도 있다 !

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 
    # 0 부터 length -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

weak = [1,3,4,9,10] dist = [3,5,7] 의 경우에

여기서 permutations로 구한 친구들 배치 순서가 5-3-7 이라고 가정해보자 , friends가 현재 [5,3,7] 이라는 거다. 

그러면 count 1 일때 , 5만큼 갈 수 있는 친구를 우선 배치한다.그럼 그 친구가 가고난 후 위치는 ?

position = weak[start] + friends[count - 1] 이고 1 + 5 = 6 이 된다.즉, 현재 친구0 이 가고 난 후 위치는 6이다. 

그런데 아직 우리는 9 랑 10 지점도 가야한다. 아직 weak 가 남아있는지 판단하는 부분이

if position< weak[index] 이다 

판단할 때는 start 시작지점부터 10이 있는 마지막 지점까지 for문으로 하나씩 점검하면 간단하다 !