구현 알고리즘 : 외벽 점검 - 파이썬 (python)

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

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

 

* 아이디어 1 👎

(1) weak 배열 간의 거리를 구한다.

   예를 들어, 테스트케이스 1의 경우에는 weak = [1, 5, 6, 10] 이므로 (외벽의 길이 n = 12)

   weak 배열 간의 거리 weak_gap = [4, 1, 4, 3] 이 된다.

(2) weak_gap에서 가장 큰 값 다음 인덱스부터 가장 큰 값 앞까지 순회한다.

   위의 경우에는 weak_gap[2] = 4가 max 값이므로 weak_gap[3], weak_gap[0], weak_gap[1] 순으로 검사한다.

(3) dist는 내림차순으로 큰 값에서 작은 값으로 정렬하고, dist = [4, 3, 2, 1]

    dist[0] 부터 weak_gap[3] ~ 비교한다.

(4) dist[0] = 4, weak 3 제거 (answer++)
    dist[1] = 3, weak 4 제거 X 
    dist[1] = 3, weak 1 제거 (answer++)

 

테스트케이스 2에도 위 알고리즘을 적용해보자

(1) weak 배열 간의 거리를 구한다.

    weak_gap: [2, 1, 5, 1, 3]

(2) 시작 인덱스: 3

(3) dist: [7, 5, 3]

(4) dist[0] = 7, weak 1 제거 (7 - 1 = 6) 

    dist[0] = 7, weak 3 제거 (6 - 3 = 3)

    dist[0] = 7, weak 2 제거 (3 - 2 = 1)

    dist[0] = 7, weak 1 제거 (1 - 1 = 1) (answer++)

 

단순히 비교만하고 삭제할 것이 아니라 weak를 없앨 때 마다 sum을 구하고 그 값을 dist의 값과 비교해서

dist의 값이 더 크면 dist에서 weak의 값을 빼고 ... 등의 과정이 필요하다.

테스트케이스 1의 (4)에서는 이 방법과 조금 다른 조건을 또 추가해야 한다.

(dist[1] = 3, weak 4 에서 weak를 제거하지 않고 다음 weak로 넘어가는 경우)

 

* 아이디어 2 👎

외벽의 길이 n에서 n = n - weak_gap[i] 을 하는 경우도 고려해봤지만

모든 테스트케이스에서 공통적으로 적용하기가 어렵다.

 

* 교재 풀이

- weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색을 이용한다.

- 전체 친구의 수(dist의 길이)는 최대 8이므로 모든 친구를 무작위로 나열하는 모든 경우의 수를 확인한다. → 순열

- 원형으로 나열된 데이터를 처리하는 경우에는, 길이를 2배로 늘려서 일자 형태로 변경하는 것이 좋다.

 

테스트케이스 2의 경우

n = 12

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

dist = [3, 5, 7]

 

(1) 취약한 지점을 2번 나열해서 원형을 일자 형태로 만든다.

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

 

(2) 각 친구를 나열하는 모든 경우의 수는 3! = 6

[3m, 5m, 7m]

[3m, 7m, 5m]

[5m, 3m, 7m]

[5m, 7m, 3m]

[7m, 3m, 5m]

[7m, 5m, 3m]

 

(3) 위 각각의 경우에 대하여 4개의 취약한 지점을 모두 검사할 수 있는지 확인하면 된다.

[7m, 3m, 5m] 의 경우 [1, 3, 4, 9, 10, 13, 15, 16, 21, 22]

7m를 이동할 수 있는 친구가 9m에서 출발하여 5곳을 방문한다면 7m만 이동해도 모든 취약 지점을 점검할 수 있다.

 

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
    # 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

코드 제출 시 테스트케이스 22번만 통과하지 못하는데 반례를 못찾았다 .. 😓

solution(200, [0, 100], [1, 1]) 입력 시 result = 2 가 반례라는데 여기서도 2가 잘 출력된다.

다른 문제 풀고 다시 돌아와서 스스로 처음부터 다시 짜봐야겠다 !

 

 

 

https://github.com/501501/codingTest/blob/master/%EA%B5%AC%ED%98%84/A14.py

GitHub - 501501/codingTest: 이것이 취업을 위한 코딩테스트다 with 파이썬