[Implementation] 이코테 “외벽 점검” Python 풀이

문제

• 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함게 직접 리모델링하기로 했습니다.
• 레스토랑이 있는 곳은 스노우타운으로 매운 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.
• 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며,
• 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다.
• 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다.
• 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다.
• 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에,
• 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다.
• 편의상 레스토랑의 정북 방향 지점을 0으로 나타내며,
• 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다.
• 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
• 외벽의 길이 n, 취약 지점의 위치가 딤긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때,
• 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최솟값을 return하도록 solution 함수를 완성해주세요.

제한 조건

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

입출력 예시

<n>
12

<weak>
[1, 5, 6, 10]

<dist>
[1, 2, 3, 4]

<result>
2

<n>
12

<weak>
[1, 3, 4, 9, 10]

<dist>
[3, 5, 7]

<result>
1

입출력 예에 대한 설명

• 입출력 예 #1

  • 원형 레스토랑에서 외벽의 취약 지점의 위치는 다음과 같습니다.

    

  • 친구들을 투입하는 예시 중 하나는 다음과 같습니다.

    • 4m를 이동할 수 있는 친구는 10m 지점에서 출발해 시계방향으로 돌아 1m 위치에 있는 취약 지점에서 외벽 점검을 마칩니다.
    • 2m를 이동할 수 있는 친구는 4.5m 지점에서 출발해 6.5m 지점에서 외벽 점검을 마칩니다.

  • 그 외에 여러 방법들이 있지만, 두 명보다 적은 친구를 투입하는 방법은 없습니다.

  • 따라서 친구를 최소 두 명 투입해야 합니다.

• 입출력 예 #2

  • 원형 레스토랑에서 외벽의 취약 지점의 위치는 다음과 같습니다.

    

  • 7m를 이동할 수 있는 친구가 4m 지점에서 출발해 반시계 방향으로 점검을 돌면 모든 취약 지점을 점검할 수 있습니다.

  • 따라서 친구를 최소 한 명 투입하면 됩니다.

풀이

• weak, dist 리스트와 같이, 주어지는 데이터의 개수가 적을 때는, 모든 경우를 일일이 확인하는 완전 탐색으로 문제에 접근해볼 수 있다.
• 문제에서 찾고자 하는 값은 ‘투입해야 하는 친구 수의 최솟값'이다.
• 이때 전체 친구의 수(dist의 길이)는 최대 8이다.
• 따라서 모든 친구를 무작위로 나열하는 모든 순열의 개수를 계산해보면, 8P8 = 8! = 40,320 으로 충분히 계산 가능한 경우의 수가 된다.
• 따라서 친구를 나열하는 모든 경우의 수를 각각 확인하여, 친구를 최소 몇 명 배치하면 되는지 계산하면 문제를 해결할 수 있다.
• 또한, 문제에서는 취약한 지점들이 원형으로 구성되어 있다고 설명하고 있다.
• 이처럼 원형으로 나열된 데이터를 처리하는 경우에는,
• 문제 풀이를 간단히 하기 위하여, 데이터의 길이를 2배 늘려서 ‘원형'을 ‘일자 형태’로 만드는 작업을 해주면 유리하다.
• 문제에서 제시된 입출력 예시 2를 확인해보자.
  • 3명의 친구가 있고, 각각 이동할 수 있는 거리가 3m, 5m, 7m이며, 취약한 지점은 1, 3, 4, 9, 10 이라고 한다.
  • 그러면 먼저 취약한 지점을 나타내는 리스트를 2배 늘려서 ‘원형'을 ‘일자 형태’로 만든다.
    • 취약한 지점 : 1, 3, 4, 9, 10, 13, 15, 16, 21, 22
  • 이제 각 친구를 나열하는 모든 경우의 수는 3! = 6가지를 순서대로 사용하여,
  • 각 조합이 연속된 5개의 취약한 지점을 확인할 수 있는지 파악한다.
    • 예를 들어, 사용하려는 조합이 [7, 3, 5]일 경우,
    • 1부터 7, 3, 5 를 사용한다면, [1, 3, 4], [9, 10] 으로 2명이 사용된다.
    • 3부터 7, 3, 5 를 사용한다면, [3, 4, 9, 10], [13] 으로 2명이 사용된다.
    • 4부터 7, 3, 5 를 사용한다면, [4, 9, 10], [13], [15] 로 3명이 사용된다.
    • 9부터 7, 3, 5 를 사용한다면, [9, 10, 13, 15, 16] 으로 1명이 사용된다.
  • 따라서, 7m를 움직이는 친구 1명을 통해, 취약한 지점을 방문할 수 있다.

예제 코드

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

from itertools import permutations

def solution(n, weak, dist):

    # 원본 취약 지점 리스트의 길이
    origin_weak_len = len(weak)
    # 취약 지점 리스트의 길이를 2배 늘려 원형 형태를 일자 형태로 변환
    for i in range(origin_weak_len):
        weak.append(weak[i] + n)

    # 친구 순열 조합 생성
    total_friends = list(permutations(dist, len(dist)))

    # 사용된 친구의 최소 개수
    # 마지막 단계까지 아무 조합으로도 모든 취약 지점 탐색이 불가능했는지 확인하기 위해 +1
    result = len(dist) + 1

    # 변환된 취약 지점 리스트의 탐색 시작 인덱스를 결정
    for start_weak in range(origin_weak_len):

        # 친구 순열 조합을 순서대로 사용
        for friends in total_friends:

            # 투입된 친구의 수
            count = 1

            # 투입된 친구가 확인할 수 있는 마지막 위치
            position = weak[start_weak] + friends[count-1]

            # 변환된 취약 지점 리스트의 일정 구간을 탐색
            for search_index in range(start_weak, start_weak + origin_weak_len):

                # 마지막까지 탐색된 위치보다 현재 취약 지점의 값이 크다면
                if (weak[search_index] > position):
                    # 친구 추가
                    count +=1
                    # 친구들을 더 이상 투입할 수 없을 경우
                    if (count > len(dist)):
                        break
                    # 마지막까지 확인된 위치를 업데이트
                    position = weak[search_index] + friends[count-1]

            # 투입된 친구의 최소값을 계산
            result = min(result, count)

    # 친구들을 모두 투입해도 탐색하기 어려울 경우
    if (result > len(dist)):
        return -1

    return result

참고

• 이것이 취업을 위한 코딩 테스트다. with python