[프로그래머스 / Level3] 외벽 점검 (Java)

문제 보기

사용한 것

• 순열을 구하기 위한 DFS

풀이 방법

• 가장 먼 거리를 점검할 수 있는 친구를 우선적으로 배치하기 위하여 distances를 내림차순으로 정렬한다.
• for문을 돌며numOfFriends를 1부터 최대까지 순회한다.
  • 현재 numOfFriends 만큼 순열을 구해 order에 저장한다.
    • order를 통하여 벽을 모두 점검할 수 있는지 판단한다.
    • 점검을 시작하는 위치에 따라서 정답이 달라질 수 있기 때문에 가능한 모든 시작 위치로 shiftedWeekPoints를 초기화 하면서 진행한다.

코드

class Solution {

    private int lenOfOuterWall;
    private int[] weekPoints;
    private int numOfWeekPoints;
    private Integer[] distances;
    private int maxNumOfFriends;

    public int solution(int n, int[] weak, int[] dist) {
        lenOfOuterWall = n;
        weekPoints = weak;
        numOfWeekPoints = weekPoints.length;
        distances = Arrays.stream(dist).boxed().toArray(Integer[]::new);
        Arrays.sort(distances, Comparator.reverseOrder());
        maxNumOfFriends = dist.length;
        return findMinNumOfFriends();
    }

    private int findMinNumOfFriends() {
        int minNumOfFriends = -1;
        for (int i = 1; i <= maxNumOfFriends; i++) {
            boolean[] visited = new boolean[i];
            int[] order = new int[i];
            if (dfs(i, 0, visited, order)) {
                minNumOfFriends = i;
                break;
            }
        }
        return minNumOfFriends;
    }

    private boolean dfs(int numOfFriends, int depth, boolean[] visited, int[] order) {
        if (depth == numOfFriends) {
            return canCheckAll(numOfFriends, order);
        }
        for (int i = 0; i < numOfFriends; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            order[depth] = distances[i];
            if (dfs(numOfFriends, depth + 1, visited, order)) {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }

    private boolean canCheckAll(int numOfFriends, int[] order) {
        boolean ret = false;
        for (int i = 0; i < numOfWeekPoints; i++) {
            int[] shiftedWeekPoints = getShiftedWeekPoints(i);
            int idx = -1;
            for (int j = 0; j < numOfFriends; j++) {
                int limit = shiftedWeekPoints[idx + 1] + order[j];
                for (int k = idx + 1; k < numOfWeekPoints; k++) {
                    if (shiftedWeekPoints[k] <= limit) {
                        idx = k;
                    } else {
                        break;
                    }
                }
            }
            if (idx == numOfWeekPoints - 1) {
                ret = true;
                break;
            }
        }
        return ret;
    }

    private int[] getShiftedWeekPoints(int distance) {
        int[] shiftedWeekPoints = new int[numOfWeekPoints];
        for (int j = 0; j < numOfWeekPoints - distance; j++) {
            shiftedWeekPoints[j] = weekPoints[j + distance];
        }
        for (int j = numOfWeekPoints - distance; j < numOfWeekPoints; j++) {
            shiftedWeekPoints[j] = weekPoints[j + distance - numOfWeekPoints] + lenOfOuterWall;
        }
        return shiftedWeekPoints;
    }
}