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

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

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

2021-01-17

---

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Solution60062 {
    public static int di[], we[], arr[], answer;
    public static boolean vtd[];
    public static List<Integer> list;
    
    public static void friends() {
        int count = 0; // 친구 수
        int check = 0;
        int prev = 0;
        loop: for (int k = 0; k < arr.length; k++) {
            if (prev >= we.length)
                break;
            int num = list.get(prev) + di[arr[k]];
            for (int p = prev; p < we.length; p++) {
                if (list.get(p) <= num) {
                    check++;
                    if (p == we.length - 1) {
                        count++;
                        break loop;
                    }
                } else {
                    prev = p;
                    break;
                }
            }
            count++;
        }
 
        if (check == we.length) {
            answer = Math.min(answer, count);
        }
    }
    
    public static void solve(int cnt) {
        if(cnt == di.length) {
            friends();
            return; 
        }
        
        for(int i = 0; i < di.length; i++) {
            if(!vtd[i]) {
                vtd[i] = true;
                arr[cnt] = i;
                solve(cnt+1);
                vtd[i] = false;
            }
        }
    }
    
    public static int solution(int n, int[] weak, int[] dist) {
        answer = 987654321;
        di = dist;
        we = weak;
        arr = new int[dist.length];
        vtd = new boolean[dist.length];
        Arrays.sort(dist);
        
        for (int i = 0; i < weak.length; i++) {
            list = new ArrayList<>();
            // make
            for (int j = i; j < i + weak.length; j++) {
                if (j < weak.length)
                    list.add(weak[j]);
                else {
                    list.add(weak[j - weak.length] + n);
                }
            }
            solve(0);
        }
 
        if (answer == 987654321)
            return -1;
        return answer;
    }
 
    public static void main(String[] args) {
//        int n = 12;
        int n = 200;
//        int w[] = {1, 5, 6, 4};
//        int d[] = {1, 2, 3, 4};
//        int w[] = {1, 3, 4, 9, 10};
//        int d[] = {3, 5, 7};
        int w[] = { 0, 10, 50, 80, 120, 160 }; // 6, 10, 12, 14
        int d[] = { 1, 10, 5, 40, 30 };
 
        System.out.println(solution(n, w, d));
    }
}
 

#문제풀이 

1. weak를 직선으로 생각하고, 나올 수 있는 조합을 다 구한다. 
weak 하나의 조합에 한 번씩 수행(2, 3)을 한다.

2. 수행은 첫번째로는 dist를 새로 조합한다. 처음에는 dist 무조건 큰 순서로만 하면 되겠지 했다가, 테스트 케이스 6, 10, 12, 14를 틀렸었다. dist를 조합 할 수 있는 모든 경우의 수를 따지고 그 하나의 조합에서 한 번씩 또다른 수행(3)을 한다.

3. 위에서 만든 weak를 앞에서부터 차레대로 체크해서, 현재 dist의 값에서 취약점을 체크할 수 있는지 체크한다. 체크가 가능한 경우 check++를 해주고 불가능한 경우 그 시작점을 prev에 저장해두었다. 이 시점에서 cont++를 해주었다.
그리고 또 다른 새로운 dist값을 불러와서 weak를 체크해준다. 가능한만큼 돌고, 더 이상 할 수 없을 때까지 반복한다.
만약, 이렇게 해서 check 된 값이 weak의 length와 같다면, 전부 점검할 수 있는 경우이므로 answer를 업데이트 시켜주고 아닌 경우는 패쓰한다.

 

정리하면서 풀었다기 보다는 의식의 흐름대로 풀어서 코드가 좀 지저분한 것 같다