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

문제 링크

• 외벽 점검

풀이

• 주어진 값들의 범위가 크지 않아서 완전 탐색이 적합하다고 판단하였다.
• weak에서 가장 넓은 간격을 끊어서 시작 지점을 하나로 추렸다. 모두 간격이 같다면 시작 지점을 아무 요소로 잡아도 상관없다.
• 위의 기준으로 정렬된 weak 배열을 편의상 오름차순이 되도록 값을 조정하였다. 여기서의 오름차순은 요소의 위치를 조정한 것이 아니다.
• 이렇게 하면 dist에 대한 완전탐색 문제로 단순화된다.

코드

import java.util.*;

class Solution {
    boolean[] isUsed;
    int answer = Integer.MAX_VALUE;
    
    public int solution(int n, int[] weak, int[] dist) {
        isUsed = new boolean[dist.length];
        sort(weak, n);
        dfs(dist, weak, 0, 0, n);
        if (answer == Integer.MAX_VALUE) {
            return -1;
        }
        return answer;
    }
    
    private void dfs(int[] dist, int[] weak, int index, int depth, int n) {
        
        for (int i = 0; i < dist.length; i++) {
            if (!isUsed[i]) {
                isUsed[i] = true;
                int nextIndex = index + 1;
                int nextDistance = (weak[index] + dist[i]) % n;
                
                while (nextIndex < weak.length) {
                    if (nextDistance >= weak[nextIndex]) {
                        nextIndex++;
                    } else {
                        break;
                    }
                }

                // System.out.println(index + " " + nextIndex + " " + nextDistance);
                if (nextIndex >= weak.length) {
                    answer = Math.min(answer, depth + 1);
                } else {
                    dfs(dist, weak, nextIndex, depth + 1, n);
                }
                
                isUsed[i] = false;
            }
        }
    }
    
    private void sort(int[] weak, int n) {
        int index = getStartIndex(weak, n);
        int[] tmp = new int[weak.length];
        
        for (int i = index; i < index + weak.length; i++) {
            tmp[i - index] = weak[i % weak.length];
        }
        
        for (int i = 1; i < weak.length; i++) {
            if (tmp[i] < tmp[i - 1]) {
                tmp[i] += n;
            }
        }
        int fistNum = tmp[0];
        for (int i = 0; i < weak.length; i++) {
            weak[i] = tmp[i] - fistNum;
        }
    }
    
    private int getStartIndex(int[] weak, int n) {
        int index = 0;
        int maxDistance = weak[0] + n - weak[weak.length - 1];
        for (int i = 1; i < weak.length; i++) {
            if (weak[i] - weak[i - 1] > maxDistance) {
                index = i;
                maxDistance = weak[i] - weak[i - 1];
            }
        }
        return index;
    }
}