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

원형 제방 점검 문제 해결 방법

문제 이해

• n: 원의 둘레 길이
• weak: 터치포인트 배열 (예: [1,5,6,7])
• dist: 각 친구의 최대 이동거리 배열

해결 접근법

1. 구간 생성

weak 포인트들을 기반으로 두 가지 구간을 만듭니다:

예시: weak = [1,5,6,7]

1. 연속 구간: [1~5, 5~6, 6~7] → 거리: [4, 1, 1]
2. 원형 구간: [7~n, n~1, 1~5, 5~6] → 거리: [n-7, 1, 4, 1]

2. 구간별 거리 계산

// 연속 구간 거리
const continuousDistances = [4, 1, 1];

// 원형 구간 거리  
const circularDistances = [n-7, 1, 4, 1];

3. dist 사용 전략

각 구간에서:

1. 구간 내 거리 합을 계산
2. 가장 큰 dist부터 사용하여 구간을 커버
3. 남은 거리는 다음 큰 dist로 처리
4. 모든 구간을 커버할 때까지 반복

4. 최적화

• 두 구간 모두에서 최소 dist 개수를 찾음
• 각 구간별로 독립적으로 계산 후 최솟값 선택

핵심

1. 구간 기반 접근: weak 포인트들을 구간으로 나누어 처리
2. 원형 처리: 원의 특성을 고려한 구간 분할
3. 탐욕적 선택: 가장 큰 dist부터 사용하여 효율성 극대화
4. 최적화: 여러 구간 중 최소 dist 사용량 선택

수정

테스트 케이스를 분석해보겠습니다.

입력: n=12, weak=[1,5,6,10], dist=[1,2,3,4]

현재 코드의 문제점을 찾아보겠습니다:

[1 tool called]

문제를 발견했습니다! 현재 알고리즘의 핵심 문제점은 구간을 연속적으로만 커버하려고 한다는 것입니다.

실제로는: dist=4로 15 구간(거리 4)을 커버하고, dist=3으로 610 구간(거리 4)을 커버하면 총 2개로 해결 가능합니다.

하지만 현재 코드는 연속된 구간만 하나의 dist로 커버하려고 해서 실패합니다.

올바른 접근법으로 수정하겠습니다:

[1 tool called]

이제 테스트해보겠습니다:

[1 tool called]

완벽합니다! 이제 정답이 나옵니다.

문제 해결 과정

기존 구간 기반 접근법의 문제점:

• 구간을 연속적으로만 커버하려고 함
• 실제로는 불연속 구간도 하나의 dist로 커버 가능

수정된 접근법:

• 백트래킹 방식: 각 dist를 사용하여 가능한 모든 조합을 시도
• 원형 고려: 각 weak 포인트를 시작점으로 하여 원형 처리
• 재귀적 해결: 남은 weak 포인트들과 dist로 재귀 호출

테스트 케이스 분석:

• n=12, weak=[1,5,6,10], dist=[1,2,3,4]
• dist=4로 15 구간 커버, dist=3으로 610 구간 커버
• 총 2개의 dist로 해결 가능 ✅

이제 구간 기반 접근법의 한계를 극복하고 올바른 해결책을 구현했습니다!