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

[52] 외벽 점검

책 구매하기

문제 정보

• 분류: 백트래킹
• 정답률: 30%
• 권장 시간 복잡도: O(W * D! * D)
• 핵심 키워드: 원형, 순열, 취약 지점, 최소 인원
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/60062

문제를 읽을 때 체크할 포인트

원형 문제라서 시작점을 고정하면 틀리기 쉽다. 취약 지점을 일자로 펼치고, 친구 투입 순서를 순열로 돌려서 몇 명이면 모두 덮는지 확인해야 한다.

한 번의 선택으로 답이 확정되지 않고, 가능한 경우를 조건에 맞게 잘라 가며 끝까지 봐야 하는 유형이다. 그래서 '무엇을 상태로 들고 갈지'를 먼저 정하는 게 중요하다.

풀이 흐름

1. weak를 길이 2배로 확장해 원형을 선형처럼 다룬다.
2. 시작점마다 dist 순열을 하나씩 적용해 커버 가능한 마지막 위치를 갱신한다.
3. 모든 취약 지점을 덮은 경우 사용한 친구 수 최솟값을 갱신한다.

구현할 때 놓치기 쉬운 부분

시작 지점, 친구를 투입하는 순서, 원형 외벽을 선형으로 펼쳐 보는 방식이 모두 중요하다. 원형 그대로만 보거나 순열을 생략하면 최소 인원 수를 찾기 어렵다.

파이썬 정답 코드

from itertools import permutations

def solution(n, weak, dist):
  # weak를 길이 2배로 확장해 원형을 선형처럼 다룬다.
  length = len(weak)
  extended = weak + [w + n for w in weak]
  answer = len(dist) + 1

  # 시작점마다 dist 순열을 하나씩 적용해 커버 가능한 마지막 위치를 갱신한다.
  for start in range(length):
    # 모든 취약 지점을 덮은 경우 사용한 친구 수 최솟값을 갱신한다.
    for friends in permutations(dist):
      count = 1
      limit = extended[start] + friends[count - 1]

      for idx in range(start, start + length):
        if extended[idx] > limit:
          count += 1
          if count > len(dist):
            break
          limit = extended[idx] + friends[count - 1]

      answer = min(answer, count)

  return answer if answer <= len(dist) else -1

시간 복잡도

W는 취약 지점 수, D는 친구 수이다.

출발 기준점이 W개 있고, 친구를 배치하는 순서를 모두 시도하면 D!가지가 생긴다. 순열 하나가 실제로 취약 지점을 덮는지 확인하는 데 다시 D 정도가 들어 전체가 O(W * D! * D)이다.

따라서 시간 복잡도는 O(W * D! * D)이다.