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

[외벽 점검]

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

프로그래머스

 

* 조건

1. 외벽의 길이(n)이 주어진다
2. 취약점의 위치(weak[])가 주어진다
3. 점검이 가능한 각각 친구들의 시간(dist[])이 주어진다
4. 친구들을 모두 투입해도 모두 점검이 불가능하다면 -1을 리턴한다

 

 

* 알고리즘

• 브루트 포스

 

 

* 로직

• 점검이 가능한 친구들의 시간을 순열을 활용해 경우의 수를 고려한다
• 각 경우의 수가 존재할 때 점검이 가능한지 판단한다
  • 취약점의 첫 번째 인덱스부터 출발점이라고 생각한다
  • 출발점을 기준으로 한 바퀴를 돌 때 (현재 출발점 + n)의 크기만큼 돌 수 있게 설정한다
  • 만약 출발점과 그 다음 취약점의 거리가 사용 가능한 친구의 시간보다 크다면
    => 현재 친구의 시간으로는 더이상 점검이 불가능하다
  • 만약 친구의 시간이 더 크다면
    => 점검이 가능하기 때문에 그 다음 취약점까지 점검이 가능한지 판단한다
  • 첫 번째 인덱스를 출발지로 했을 경우를 고려했다면 그 다음 인덱스를 출발지로 설정하고 이를 반복한다

 

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Problem_Exteriorwall {
    static int Nsize;
    static int[] weakPoint;
    static LinkedList<Integer> weak_expand;

    static boolean[] checked;
    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int n = 12;
        int[] weak = {1, 5, 6, 10};
        int[] dist = {1, 2, 3, 4};

        int answer = solution(n, weak, dist);
        System.out.println(answer);
    }

    public static int solution(int n, int[] weak, int[] dist) {
        int answer = 0;
        Nsize = n;
        weakPoint = weak.clone();
        Arrays.sort(dist);
        checked = new boolean[dist.length];

		//출발지를 기준으로 한바퀴를 돌 때 nSize만큼 늘려주기 위해
        weak_expand = new LinkedList<>();
        for(int i=0; i<weakPoint.length; ++i)
            weak_expand.add(weakPoint[i]);

        for(int i=0; i<weakPoint.length; ++i)
            weak_expand.add(weakPoint[i] + Nsize);


        int count = 0;
        //친구가 검사 가능한 거리 -> 순열
        LinkedList<Integer> list = new LinkedList<>();
        makePermutation(0, count, list, dist);

        if(result == Integer.MAX_VALUE) answer = -1;
        else answer = result;

        return answer;
    }

    private static void makePermutation(int index, int count, LinkedList<Integer> list, int[] dist) {
        if(count == dist.length){
            deterPossible(list);
            return;
        }

        for(int i=0; i<dist.length; ++i){
            if(!checked[i]){
                checked[i] = true;
                list.add(dist[i]);
                makePermutation(i, count+1, list, dist);
                list.removeLast();
                checked[i] = false;
            }
        }
    }

    private static void deterPossible(LinkedList<Integer> friendLists) {
        //시작점
        for(int i=0; i<weakPoint.length; ++i){
            int idx = 0;
            int startPoint = weak_expand.get(i);
            boolean mark = false;

            for(int j=i; j<i + weakPoint.length; ++j){
                //두 점 사이의 거리가 검사 가능한 친구의 거리보다 크다면 -> 커버가 불가능
                //-> 해당 지점을 출발지로 설정
                if(weak_expand.get(j) - startPoint > friendLists.get(idx)){
                    startPoint = weak_expand.get(j);
                    idx++;

                    //모든 친구를 다 사용한 경우
                    if(idx == friendLists.size()){
                        mark = true;
                        break;
                    }
                }
            }

            //모든 친구를 사용하지 않고도 가능하다면
            if(!mark) result = Math.min(result, idx+1);
        }
        return;
    }
}