14_외벽 점검

프로그래머스

구현 문제다.

구현이 쉽지 않다.

내가 코드를 짜면 코드가 너무 복잡해진다.

그래서 풀이를 볼 수 밖에 없었다.

 

---

풀이

 

제한 조건을 봤을 때, weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색 가능하다. -> 이건 알고 있었음

문제에서 찾고자 하는 것은 "투입해야 하는 친구 수의 최솟값"이다.

이 때 전체 친구의 수(dist의 길이)는 최대 8이므로, 모든 친구를 무작위로 나열하는 모든 순열의 개수를 계산하면 8P8 = 40,320으로 충분히 계산가능하다. -> 이것도 알고 있었음

그러므로 친구를 나열하는 모든 경우의 수를 각각 확인해 친구를 최소 몇 명 배치하면 되는지 계산하면 문제를 해결할 수 있다.

 

이 문제에서 까다로운 점은 취약한 지점들이 원형으로 배치되어 있다는 것이다.

이처럼 원형으로 나열된 데이터를 처리하는 경우, 문제 풀이를 간단히 하기 위해, 길이를 2배로 늘려서 원형을 일자 형태로 만드는 작업을 해주면 유리하다.

 

예를 들어

weak = [1, 3, 4, 9, 10]

dist = [3, 5, 7]

일 때, 

 

weak을 2번 나열해서 원형을 일자로 만들어준다.

[1, 3, 4, 9, 10, 13, 15, 16, 21, 22]

 

그리고 모든 친구를 나열하는 경우의 수는 3! = 6가지이다.

[3, 5, 7]

[3, 7, 5]

[5, 3, 7]

[5, 7, 3]

[7, 3, 5]

[7, 5, 3]

 

위 각각의 경우에 대해 4가지 취약한 지점을 모두 검사할 수 있는지 확인한다.

 

풀이 코드

from itertools import permutations

def solution(n, weak, dist):
    # 길이를 2배로 늘려서 원형을 일자 형태로 변형
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    
    answer = len(dist) + 1 # 투입할 친구 수의 최솟값을 찾아야 하므로 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

 

어렵다 ㅎㅎ

계속 풀어서 익숙해지자