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

https://programmers.co.kr/learn/courses/30/lessons/60062

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

import java.util.*;

class Solution {
    static int answer=Integer.MAX_VALUE;
    static ArrayList<ArrayList<Integer>> perms=new ArrayList<>();
    public int solution(int n, int[] weak, int[] dist) {
        int[] w=new int[weak.length+weak.length-1];
        for (int i=0; i<w.length; i++){
            if (i<weak.length){
                w[i]=weak[i];
            }
            else{
                w[i]=weak[i-weak.length]+n;
            }
        }
        makePerm(0, dist.length, dist, new boolean[dist.length], new int[dist.length]);
        for (int i=0; i<perms.size(); i++){ //dist의 순열
            ArrayList<Integer> order=perms.get(i);
            for (int j=0; j<weak.length; j++){  //weak의 경우의 수
                int sum=0;
                int end=w[j+weak.length-1];
                int next=j;
                for (int k=0; k<order.size(); k++){
                    sum=w[next]+order.get(k);
                    if (sum>=end){
                        answer=Math.min(answer, k+1);
                        break;
                    }
                    next=findDest(sum, j, weak.length, w)+1;
                }
            }
        }
        if (answer==Integer.MAX_VALUE) return -1;
        else return answer;
    }
    public int findDest(int start, int j, int length, int[] w){ //시작점이 j이고 온 거리가 start 일때 weak의 몇번째까지 도착했나?
        for (int i=j; i<j+length; i++){
            if (w[i]>start) return i-1;
        }
        return -2;
    }
    
    public void makePerm(int cnt, int target, int[] dist, boolean[] visited, int[] res){
        if (cnt==dist.length){
            perms.add(new ArrayList<>(res.length));
            for (int i=0; i<res.length; i++){
                perms.get(perms.size()-1).add(res[i]);
            }
            return;
        }
        for (int i=0; i<dist.length; i++){
            if (visited[i]) continue;
            visited[i]=true;
            res[cnt]=dist[i];
            makePerm(cnt+1, target, dist, visited, res);
            visited[i]=false;
        }
    }
    
}

많이 까다로웠던 문제..역시 카카오......

완전탐색인건 캐치했으나 구현에서 막혀버렸다.. 다른 분들의 아이디어를 참고해서 풀었다

 

일단 순열 2개를 돌리는 식이다

- weak의 순열 (0번부터 weak의 length(이하 L)만큼 가는 경우, 1번부터 L만큼 가는 경우, 2번부터 L만큼 가는 경우 ... 마지막 번부터 L만큼 가는 경우)

-dist의 순열 perms (각 weak의 순열과 매칭할 dist의 순열, makePerm 함수에서 한꺼번에 생성해주었다)

 

weak의 순열은 w배열에서 각 0번부터~L-1번까지 시작하는 연속된 길이 L개의 배열이 된다.. 이 아이디어를 잡는게 어려웠다

 

이렇게 해서 각 perm마다, 가능한 weak의 순열을 돌려주면서 최소값을 체크하면 된다.

이때 위치를 움직일 때마다, weak의 몇번째까지 움직였는지 체크해줘서 다음 사람이 움직일 때 그 바로 다음부터 움직일 수 있도록 했다.

답을 갱신할 수 있는 조건은 sum이 end 이상이 되었을 때이다 (즉 다 방문했을 때)