Programmers - 외벽점검 with JAVA (V)

 

 

로직

1. DIst의 조합을 구한다.

2. 새로운 Weak 생성 - N 범위 넘어가거나 뒤로가는 경우를 묶기위함.

3. 기존의 weak의 위치에서 출발해 weak의 길이만큼 점검시 종료

 

예시

weak = [1, 2, 3, 4] , n = 10

new_weak = [1, 2, 3, 4, 11, 12, 13, 14]

- 1부터 출발 [1, 2, 3, 4] 모두 검사 가능한지 체크

- 2부터 출발 [2, 3, 4, 11] 모두 검사 가능한지 체크

 

4. 친구의 수가 부족하다면 늘려서 가장 적게 친구를 사용할때가 정답

 

 

 

 

코드

import java.util.*;
class Solution {
    public static List<List<Integer>> check = new ArrayList<>();
    public int solution(int n, int[] weak, int[] dist) {
        // dist 경우의 수 구하기
        find(new ArrayList<>(), dist, new boolean[dist.length]);
        // 기본 설정(초기값, 맵 설정)
        int answer = dist.length+1;
        int length = weak.length;
        List<Integer> new_weak = new ArrayList<>();
        for(int w : weak){
            new_weak.add(w);
            new_weak.add(n+w);
        }
        Collections.sort(new_weak);
        // 공사 시작점 weak에서 선택
        for(int start=0; start<length; start++){
            // dist의 조합마다 처리
            for(List<Integer> friends : check){
                // 첫번째 친구가 start 지점 공사
                int position = new_weak.get(start)+friends.get(0);
                int index = 1;
                int count = 1;
                // start부터 weak의 크기만큼 처리했는지 확인
                for(int now=start; now<start+length; now++){
                    if(position < new_weak.get(now)){
                        // 모든 친구 다 사용시 멈춤
                        count += 1;
                        if(count > dist.length){
                            break;
                        }
                        position = new_weak.get(now)+friends.get(index);
                        index += 1;
                    }
                }
                answer = Math.min(answer, count);
            }
        }
        if(answer > dist.length){
            return -1;
        }
        return answer;
    }
    public static void find(List<Integer> result,int[] dist, boolean[] visited){
        if(result.size() == dist.length){
            check.add(new ArrayList<>(result));
            return;
        }
        for(int i=0; i<dist.length; i++){
            if(!visited[i]){
                visited[i] = true;
                result.add(dist[i]);
                find(result, dist, visited);
                result.remove(result.size()-1);
                visited[i] = false;
            }
        }
    }
}