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

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/60062?language=java 

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

 

- 참고 링크 : 

https://gre-eny.tistory.com/168

[java] 프로그래머스 (외벽 점검) Level 3

https://leveloper.tistory.com/101

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

https://dev-note-97.tistory.com/241

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

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

- 풀이

 : 케이스 숫자를 보고 완전 탐색은 떠올렸지만 나머지 아이디어가 떠오르지 않아 많은 링크를 참고했다.

 : 완전 탐색, 순열 문제였다.

 

 1. 원형으로 된 벽을 직선으로 쭉 핀 뒤에 크기를 늘리고 레일 크기대로 하나씩 점검한다.

   ( ex. n=12, weak = [1, 5, 6, 10] -> [1, 5, 6, 10, 13, 17, 18] -> [1, 5, 6, 10], [5, 6, 10, 13], [6, 10, 13, 17], [10, 13, 17, 18] )

 2. 친구들이 점검할 수 있는 길이를 순열로 체크하면서 앞에서부터 갈 수 있는 길이를 체크한다.

   ( ex. dist = [1,2,3] -> [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 순서로 친구들이 확인이 가능하다)

 3. 1번과 2번을 모두 검사하면서 차례로 확인하고 길을 모두 갈 수 있다면 ok, 갈 수 없다면 해당 순열 순서의 방법으로는 불가능하다는 뜻이 된다.

   ( ex. weak = [5, 6, 10, 13] , [4,1,2,3] -> 정답과는 다르지만 ok인 경우,

          5에서 시작해서 4 이동 => 9 (= 5, 6 취약 지점 커버)

          10으로 바로 이동 (9와 10 사이에는 취약 지점이 없기 때문)

          10에서 시작해서 1 이동 => 11 (= 10 취약 지점 커버)

          13으로 바로 이동 (11과 13 사이에는 취약 지점이 없기 때문)

          13에서 시작해서 2 이동 => 13 (= 13 취약 지점 커버 == 1 취약 지점 커버)

    )

 : 이를 모든 케이스에 대해서 검사하면서 최소 길이를 구하면 되고 모두 불가능하다면 -1을 리턴한다.

 

 - 답

class Solution {
    private boolean[] visitedPerm;
    private int[] distPerm;
    private int[] weakStretched;
    private int answer;
    
    public int solution(int n, int[] weak, int[] dist) {
        visitedPerm = new boolean[dist.length];
        distPerm = new int[dist.length];
        weakStretched = new int[weak.length * 2];
        answer = dist.length+1;
        
        for (int i=0; i<weak.length; i++) {
            weakStretched[i] = weak[i];
            weakStretched[i+weak.length] = weak[i] + n;
        }
        
        makeDistPerm(0, dist.length, dist);
        
        return answer == dist.length + 1 ? -1 : answer;
    }
    
    private void makeDistPerm(int count, int targetCount, int[] dist) {
        if (count == targetCount) {
            isAllCheckWeak();
            return;
        }
        
        for (int i=0; i<distPerm.length; i++) {
            if (!visitedPerm[i]) {
                distPerm[count] = dist[i];
                visitedPerm[i] = true;
                makeDistPerm(count+1, targetCount, dist);
                visitedPerm[i] = false;
            }
        }
    }
    
    private void isAllCheckWeak() {
        // distPerm : dist 배열의 현재 순열 순서
        // weakStretched : 환형 부분을 직선으로 쭉 늘린 배열
        int weakLen = weakStretched.length / 2;
        int distLen = distPerm.length;
        for (int i=0; i<weakLen; i++) {
            int[] curWeak = new int[weakLen];
            for (int j=0; j<weakLen; j++) {
                curWeak[j] = weakStretched[j+i];
            }
            
            check(curWeak, distPerm);
        }
    }
    
    private void check(int[] curWeak, int[] distPerm) {
        int currentIdx = 0;
        int count = 0;
        int weakLen = curWeak.length;
        int distLen = distPerm.length;
        
        while (currentIdx < weakLen && count < distLen) {
            int nextIdx = currentIdx+1;
            
            for (int i=0; i<weakLen; i++) {
                if (nextIdx >= weakLen) {
                    continue;
                }
                
                if (curWeak[currentIdx] + distPerm[count] >= curWeak[nextIdx]) {
                    nextIdx++;
                }
            }
            
            currentIdx = nextIdx;
            count++;
        }

        if (currentIdx == weakLen && count < answer) {
            answer = count;
        }
    }
}