[구현] 프로그래머스 Lv3 외벽 점검

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

프로그래머스

 

❗️ Issue 

1. 어떻게 돌아가는 원판을 표현할 것인가 

2. 친구의 배열(순서)을 어떻게 할 것인가

3. 첫번째 순서의 친구가 모든 취약점을 못메꿀 경우 다음 순서 친구를 어떻게 불러와서 메꿔야하나

💡 Solution 

1. 2배로 배열을 늘린다  

    for i in range(length):
        weak.append(weak[i]+n)

 

2. 순열로 완전탐색을 시전한다 

- 삼성 코테의 경우 itertools를 못하니까 직접 구현했는데 

 좀 어려웠던 부분이 자바는 static 쓰면서 하면 되는데 프로그래머스가 함수로 구현 되었기도 하고

 global을 남발하기가 어려웠다. 그래서 visited나 chosen을 매개변수 안에 넣어서 구현했다.

 그리고 마지막에 chosen을 전역 변수 friends 리스트에 담아서 모든 순열을 담았다 

 근데 나중에 순열의 크기가 엄청 커졌을때는 이렇게 쓰면 안될 거 같기도 하다.

 

3. 3중 for문이 들어간다. 2번째 for문까지 순열의 한 쌍을 고르고 이후 세번째 for문에서 

 position 값을 weak[idx]와 비교하는데 이과정을 떠올리기가 어려웠다. 암튼 for문 ! 을 이용하면 된다는 것!

 그리고 count 가 최대 수를 넘어가면 break 처리 해주는 것도 생각 못했다. 

 변수 크기를 증가시킬때 가지치기 할 수 있는지 염두해봐야겠다.

 

전체 코드

friends = []
def solution(n, weak, dist):
    #최소값이므로 최대값 넣어서 초기화
    answer = len(dist) + 1
    #시계 방향으로 돌기때문에 2배로 배열 만듦
    length = len(weak)
    for i in range(length):
        weak.append(weak[i]+n)
    #완전탐색 - 친구배열 순열로 만들기 
    visited = [ False for _ in range(len(dist))]
    perm(dist, len(dist),[],visited)
    # 첫 시작 부터 돌면서 모든 순열 확인
    for start in range(length):
        for chosen in friends:
            #처음 친구
            count = 1
            position = weak[start] + chosen[count-1]
            #만약 첫 친구가 못 메꿀 경우 다음 친구(idx번)가 메꾸는 for문
            for idx in range(start, start + length):
                if(position < weak[idx]):
                    count += 1
                    #만약 친구 수보다 커지면 -1인 경우 쓸모 없음 -> break
                    if count > len(dist):
                        break
                    position = weak[idx] + chosen[count-1]
            answer = min(answer,count)
    if answer > len(dist):
        answer = -1
    
    return answer

def perm(arr, r, chosen, visited):
    global friends
    if(len(chosen) == r):
        friends.append(chosen[:])
        return 
    for i in range(len(arr)):
        if(visited[i]):
            continue
        visited[i] = True
        chosen.append(arr[i])
        perm(arr, r, chosen, visited)
        chosen.pop()
        visited[i] = False