[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 외벽 점검 (Java)

 

 

프로그래머스 2020 KAKAO BLIND RECRUITMENT 외벽 점검 : https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검 | 프로그래머스

 

 

2020 카카오 공채에서 가장 어렵다고 생각되는 외벽 점검이다.

도저히 감이 안 와서 해설을 보고 나서야 풀이를 할 수 있었다. 이 글을 보기 전에 해설을 먼저 보는 것을 추천한다.

평소에 조합은 자주 사용했지만 순열은 사용해본 적이 없었는데, 이번 문제에서 처음 순열을 사용하게 되었다.

 

우선 점검을 할 친구들을 선택해야 한다.

누가 먼저 점검을 할지도 정해줘야 하므로 조합 대신 순열을 사용한다.

친구들을 선택했다면, 이제 weak의 앞에서부터 점검을 시작한다.

예를 들어, weak = [1, 5, 6, 10]이고 선택한 친구가 4, 2라면

weak의 앞에서부터 1이 얼마나 점검이 가능한지 판단한 뒤, 남은 부분부터 2가 점검을 한다.

친구 4가 1, 5를 커버할 수 있으므로 친구 2는 6부터 시작한다.

이렇게 하면 시작을 무조건 1부터 할 수 밖에 없다.

따라서 나머지 번호에서도 시작할 수 있게끔 weak 배열을 i번만큼 shift 하여 따로 저장해준다.

weak = [1, 5, 6, 10]이라고 하면,

[1, 5, 6, 10], [5, 6, 10, 13], [6, 10, 13, 17], [10, 13, 17, 18] 총 4가지의 경우가 나온다.

모든 weak의 경우를 체크해준 뒤, 가장 일찍 모든 지점을 점검한 친구들의 수를 반환해준다.

 

 

총 걸린 시간 : 2시간 30분

난이도 : ★★★★★

 

코드

class Solution {
    private int n, num = 0;
    private boolean finish = false;
    private int[] weak, dist, choice;
    private int[][] rotateWeak;

    public int solution(int n, int[] weak, int[] dist) {
        this.n = n;
        this.weak = weak;
        this.dist = dist;
        setWeak();

        for (int i = 1; i <= dist.length; i++) {
            num = i;
            choice = new int[num];
            permutation(0, new boolean[dist.length]);
            if (finish) break;
        }
        return (finish) ? num : -1;
    }

    public void permutation(int depth, boolean[] visit) {
        if (finish) return;
        if (depth == num) {
            check();
            return;
        }

        for (int i = 0; i < dist.length; i++) {
            if (!visit[i]) {
                choice[depth] = dist[i];
                visit[i] = true;
                permutation(depth + 1, visit);
                visit[i] = false;
            }
        }
    }

    public void check() {
        for (int[] weak : rotateWeak) {
            int idx = 0, start = 0;
            boolean[] visit = new boolean[weak.length];

            while (idx != num) {
                int i = start;
                int value = choice[idx++];

                for (int j = start; j < weak.length; j++) {
                    if (!(weak[i] <= weak[j] && weak[j] <= weak[i] + value)) break;
                    visit[j] = true;
                    start++;
                }
            }

            if (isFinish(visit)) {
                finish = true;
                return;
            }
        }
    }

    public boolean isFinish(boolean[] visit) {
        for (boolean bool : visit) {
            if (!bool) return false;
        }
        return true;
    }

    public void setWeak() { // weak를 0 ~ n-1번 회전하여 rotateWeak에 저장
        int len = weak.length;
        rotateWeak = new int[len][len];

        for (int i = 0; i < len; i++) {
            rotateWeak[i] = rotate(weak, i);
        }
    }

    public int[] rotate(int[] weak, int idx) {
        int len = weak.length;
        int[] result = new int[len];
        for (int i = 0; i < len; i++) {
            if (i + idx < len) result[i] = weak[i + idx];
            else result[i] = weak[i + idx - len] + n;
        }
        return result;
    }
}