프로그래머스 외벽 점검 java

코딩테스트 연습 - 외벽 점검

카카오 2020 블라인드 코테 문제 였던 외벽점검 문제다. 어려워서 설명을 봤다. 그래서 건물이 원형인 것을 활용하는 것과 순열을 활용하는 것은 이해했지만 엉뚱하게 최소 인원을 구하는 부분에서 헤멨다. 

원형 배열의 시작점을 하나씩 바꿔가면서, 친구dist의 순열을 구하여
각 경우마다 최소 필요한 친구 수를 구하기

어떤 경우에도 취약점을 모두 점검할 수 없다면 return -1
모든 취약점을 점검하는데 필요한 최소 친구 수를 구하기

1. 원형인 배열을 시계방향으로 이동할때 쉽게 다루려면, 전체 길이만큼씩 더한 것을 추가해 확정해주면 된다.

즉 weak=[1, 5, 6, 10], n=12 일때 1부터 시작하면 1, 5, 6, 10 이고

5부터 시작하면 5, 6, 10, 1+12=13 이 되듯이 계속 진행하면

weak = [1, 5, 6, 10, 13, 17, 18, 22] 가 된다. 

2. 점검을 시작할 위치를 바꾼 경우들을 구했으니, 각 위치에서 어떤 친구를 먼저 배치할 지 정해야 한다. 

이것을 dfs를 이용한 순열을 구하여 check했다. 이런 친구의 순서로 배치할 때 최소 친구가 몇명 필요할지 check

- 그런데 어차피 dist가 큰 친구부터 배치 하는 게 최소 인원을 구할 수 있다는 생각이 들어서 찾아보니 그렇게 푼 사람이 있었다.

check 부분

public int check(int start, int end, int[] permuted) {
            int friend = 1;// permuted의 index
            int pos = weak_append[start]+permuted[friend-1];// 첫 취약점의 위치+친구거리 에서 시작

            for(int i=start; i<end; i++) {
                if(pos < weak_append[i]) {// 점검 위치 벗어나면
                    friend++; // 친구추가
                    if (friend > permuted.length) return Integer.MAX_VALUE; // 친구 초과하면 실패한 방법
                    // 더이상 그 안에 취약점 없으면, 다음지점+친구거리
                    pos = weak_append[i] + permuted[friend-1];
                }
            }
            return friend;
        }

 

 

정답 전체

class Solution {
        static public int[] weak_append;
        static public int answer;
        public int solution(int n, int[] weak, int[] dist) {
            /**
             * 반시계방향도 커버하는 확장배열 만들기 1,5,6,12, 13,17,18,22
             */
            answer = Integer.MAX_VALUE;
            weak_append = new int[weak.length*2];
            int i=0;
            while (i<weak.length){
                weak_append[i] = weak[i];
                weak_append[i + weak.length] = weak[i++]+n;
            }

            for(int k=0; k<weak.length; k++) {// 시작점 옮기기
                dfs(k, 0, dist, new boolean[dist.length], new int[dist.length]);
            }

            if(answer==Integer.MAX_VALUE) return -1;

            return answer;
        }

        public void dfs(int start, int depth, int[] dist, boolean[] visited, int[] permuted) {
            /**
             * dist의 순열
             */
            if(depth==dist.length) {
                answer = Math.min(answer, check(start, start+weak_append.length/2, permuted));
                return;
            }
            for(int i=0; i<dist.length; i++) {
                if(visited[i]) continue;

                visited[i] = true;
                permuted[depth] = dist[i];
                dfs(start, depth+1, dist, visited, permuted);
                visited[i] = false;
            }
        }

        public int check(int start, int end, int[] permuted) {
			int friend = 1;// permuted의 index
            int pos = weak_append[start]+permuted[friend-1];// 첫 취약점의 위치+친구거리 에서 시작

            for(int i=start; i<end; i++) {
                if(pos < weak_append[i]) {// 점검 위치 벗어나면
                    friend++; // 친구추가
                    if (friend > permuted.length) return Integer.MAX_VALUE; // 친구 초과하면 실패한 방법
                    pos = weak_append[i] + permuted[friend-1];
                }
            }
            return friend;
        }
    }