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

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

프로그래머스

 

 

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak)
    # 위치 2배로 늘려 일자형태로
    for i in range(length):
        weak.append(weak[i] + n)
    
    # 친구의 최솟값을 찾아야 하므로, 친구 수+1 로 초기화
    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(count, answer)
    
    if answer > len(dist):
        return -1
    
    return answer

 

순열을 사용하는 완전탐색 문제..!

이 문제에서는 취약지점이 원형으로 구성되어 있는데, 이처럼 원형으로 나열된 데이터들을 처리하는 경우에는

길이를 2배로 늘려서 '원형'을 '일자 형태'로 만드는 작업을 해주면 유리하다고 한다.

또한 친구의 수가 최대 8이기 때문에 8! = 40,320 으로 완전탐색이 가능한 문제이다.

 

이 문제와 상관없이 내가 놀랐던 점은 위와 같은 코드인데

반복문을 리스트에서 돌렸을 때 실행 초과로 테스트 케이스 조차 실패했었다.

 

 

for w in weak:
        weak.append(w + n)

위 코드를 아래 코드로 바꾸자 실행 시간이 확연히 줄면서 모든 테이스케이스가 성공했다.

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

 

리스트에서 반복문을 돌리면 훨씬 느리구나...를 깨달았다.