Programmers 60062 - 외벽점검

코딩테스트 연습 - 외벽 점검 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

외벽의 총둘레는 n미터. 원형 구조. 취약점 존재

취약점을 점검하기 위해 보내야 하는 친구 수의 최솟값은?

 

어떤 친구를 어느 지점에 배치해야 할지를 결정해야 하는 문제이다.

원형 외벽을 계산하기 위해 선형으로 변경해야 한다. 배열을 두 배로 늘려 처리할 수 있다.

방향은 따로 고려하지 않아도 된다. 예를 들어 4 → 9 반시계나 9 → 4 시계나 똑같은 범위다.

가장 먼저 떠오르는 것은 dist의 최대가 8이기 때문에 8! 의 모든 경우의 수로 앞에서부터 배치해 가며 들어가는 사람들 확인해 보는 것이다.

1. dist를 통해 순열을 구성한다.
2. 취약점의 시작위치를 변경해 가며 순열을 통해 확인해 본다.
   1. 현재 취약점은 확장돼 있는 상태
   2. 커버한 개수를 통해 모든 지점을 검사했는지 확인해야 한다.
      1. 즉 해당 순열이, 해당 시작점에서, 범위를 커버가능한가 → 3중 루프가 된다.
3. 커버가 가능하다면 답을 갱신한다.

import java.util.*;

class Solution {
    
    int answer = Integer.MAX_VALUE;
    
    public int solution(int n, int[] weak, int[] dist) {
        List<int[]> result = new ArrayList<>();
        permutate(0, new int[dist.length], dist, new boolean[dist.length], result);
        check(n, result, weak);
        
        return answer;
    }
    
    private void check(int n, List<int[]> result, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = extendWeak(n, weak);
        
        for (int[] dist : result) {
            for (int start = 0; start < l; start++) {
                int cnt = 1; // start를 시작점으로 해서 투입한 사람 수
                int end = extendedWeak[start] + dist[cnt - 1];
                for (int i = start; i < start + l; i++) {
                    if (extendedWeak[i] > end) {
                        cnt++; // 추가 투입
                        if (cnt > dist.length) break;
                        end = extendedWeak[i] + dist[cnt - 1];
                    }
                }
                answer = Math.min(answer, cnt);
            }
        }
        
        if (answer > result.get(0).length) answer = -1;
    }
    
    private int[] extendWeak(int n, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = new int[2 * l];
        for (int i = 0; i < l; i++) {
            extendedWeak[i] = weak[i];
            extendedWeak[i + l] = weak[i] + n;
        }
        return extendedWeak;
    }
    
    private void permutate(int depth, int[] selected, int[] dist, boolean[] visited, List<int[]> result) {
        if (depth == dist.length) {
            result.add(selected.clone());
            return;
        }
        
        for (int i = 0; i < dist.length; i++) {
            if (visited[i]) continue;
            selected[depth] = dist[i];
            visited[i] = true;
            permutate(depth + 1, selected, dist, visited, result);
            selected[depth] = 0;
            visited[i] = false;
        }
    }
}