외벽 점검 - '카카오 2020 코딩 테스트'

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

원 모양의 외벽이 주어지고, 각 외벽에는 취약점이 존재 합니다. 이때 외벽의 취약점의 거리 배열이 주어지고, 이 취약점을 최소 인원의 친구들이 점검 할수 있는 인원 수를 반환 하는 문제 입니다. 친구들은 각자 자신들이 갈수 있는 거리 값 배열이 주어 집니다.

 

 

1. 접근

1. 최대 친구의 수가 8명 이므로, (8, 8) 순열값인 40320 이므로, 충분히 완전 탐색으로 풀수 있습니다.

2. 원 모양의 외벽을 편하게 계산 하기 위해서, 외벽을 2배 확장 시킵니다.

3. 확장 시킨 외벽을 친구들(0 ~ 최대 8명) 조합으로 탐색을 시킵니다.

4. 탐색 시 확장된 (외벽의 반 + 1) 내 에서 출발 지점을 정합니다.

5. 해당 출발 지점에서 부터 (출발 지점 + (외벽의 반 + 1))) 까지 해당 친구들 조합이 탐색을 완료 했다면, 친구 조합의 수를 반환 합니다.

6. 최소 친구 수를 반환 해야 하므로, 조합을 만들 시 1명 부터 시작 합니다.

 

 

import java.util.ArrayList;

public class Page335_2 {
    /*
     * n     weak                dist            result
     * 12    [1, 5, 6, 10]       [1, 2, 3, 4]    2
     * 12    [1, 3, 4, 9, 10]    [3, 5, 7]       1
     * */
    public static void main(String[] args) {
        int n = 12;
        int[] weak = new int[]{1, 3, 4, 9, 10};
        int[] dist = new int[]{3, 5, 7};
        System.out.print(new Page335().solution(n, weak, dist));
    }

    ArrayList<int[]> friends;

    public int solution(int n, int[] weak, int[] dist) {
        int answer = -1;
        int[] expand_weak = new int[weak.length * 2 - 1];

        // 2배로 weak 확장
        for (int i = 0; i < expand_weak.length; i++) {
            expand_weak[i] = (i < weak.length) ? weak[i] : weak[i % weak.length] + n;
        }

        for (int i = 1; i <= dist.length; i++) {
            // 출전 친구 구하기
            friends = new ArrayList<>();

            // 배열 중 i명을 뽑았을때 조합
            // i = 1 이면 친구 한명 조합
            permutation(dist, 0, i);

            //해당 친구들 조합으로 취약 지점 검사
            for (int j = 0; j < friends.size(); j++) {
                if (check(expand_weak, friends.get(j))) {
                    answer = friends.get(j).length;
                    break;
                }
            }

            if (answer != -1) break;
        }

        return answer;
    }

    boolean check(int[] weak, int[] friend) {
        int len = weak.length / 2 + 1;

        // 출발 지점 갱신
        for (int i = 0; i < len; i++) {
            // 친구 인덱스
            int friendIdx = 0;
            //출발 지점 갱신
            int startPoint = weak[i];
            boolean flag = true;

            // 출발 지점(i) 부터 ~ 취약 지점 끝(i+len) 까지
            for (int j = i; j < i + len; j++) {
                // 탐색 실패
                if (weak[j] - startPoint > friend[friendIdx]) {
                    startPoint = weak[j];
                    // 다른 친구가 이어서 검사
                    friendIdx++;

                    // 0 ~ 친구 수 까지 모두 검사했다면
                    if (friendIdx == j) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) return true;
        }
        return false;
    }

    void permutation(int[] arr, int depth, int r) {
        if (depth == r) {
            int[] tmp = new int[r];

            for (int i = 0; i < r; i++)
                tmp[i] = arr[i];

            friends.add(tmp);
        }

        for (int i = depth; i <= arr.length; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, r);
            swap(arr, depth, i);
        }
    }

    void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

 

위 문제 에서, 순열(permutation) 구현을 배울수 있었습니다. permutation(int[] arr, int depth, int r) 은 arr 배열에서, r개의 원소를 뽑아, 순서가 다른 조합을 만들어 냅니다. 여기서 depth 는 for i in (r >= depth) { i개의 조합들 } 을 만들어 냅니다.  따라서, 소스 코드에서 permutation(dist, 0, i); 는 i명을 뽑아 만들수 있는 조합들을 friends의 넣어 줍니다. 만약, permutation(dist, 1, 2); 라면, 친구들 중 2명을 뽑아 만들수 있는 조합과 1명을 뽑아 만들수 있는 조합이 모두 friends의 담깁니다. 만약 permutation(dist, 1, 3); 라면, 친구들 중 3명을 뽑아 만들수 있는 조합과 2명을 뽑아 만들수 있는 조합이 모두 friends의 담기게 됩니다.

 

 

import java.util.ArrayList;

// 순열 구하기
public class Permutation {
    private int n;
    private int r;
    private int[] now; // 현재 순열
    private ArrayList<ArrayList<Integer>> result; // 모든 순열

    public ArrayList<ArrayList<Integer>> getResult() {
        return result;
    }

    // 전체 n개 갯수 중 r개를 뽑은 조합
    public Permutation(int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<ArrayList<Integer>>();
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void permutation(int[] arr, int depth) {
        // 현재 순열의 길이가 r일 때 결과 저장
        if (depth == r) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(now[i]);
            }
            result.add(temp);
            return;
        }
        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            now[depth] = arr[depth];
            permutation(arr, depth + 1);
            swap(arr, i, depth);
        }
    }
}

 

따라서, 순열 로직을 따로 class로 빼면 이와 같이 됩니다.