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

문제

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

프로그래머스

 

 

 

 

코드

import java.util.*;

class Permutation {
    private int n;
    private int r;
    private int[] now;  // 현재 순열
    private ArrayList<ArrayList<Integer>> result;   // 모든 순열

    public ArrayList<ArrayList<Integer>> getResult() {
        return result;
    }

    public Permutation(int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<ArrayList<Integer>>();
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void permutation(int[] arr, int depth) {
        // 현재 순열의 길이가 r일 때 결과 저장
        if (depth == r) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                temp.add(now[i]);
            }
            result.add(temp);
            return;
        }
        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            now[depth] = arr[depth];
            permutation(arr, depth + 1);
            swap(arr, i, depth);
        }
    }
}

class Solution {
    public int solution(int n, int[] weak, int[] dist) {
        // 길이를 2배로 늘려서 원형을 일자로 변경
        ArrayList<Integer> weakList = new ArrayList<>();
        for (int i = 0; i < weak.length; i++) {
            weakList.add(weak[i]);
        }
        for (int i = 0; i < weak.length; i++) {
            weakList.add(weak[i] + n);
        }
        int answer = dist.length + 1;
        // 친구 정보를 이용해 모든 순열 계산
        Permutation perm = new Permutation(dist.length, dist.length);
        perm.permutation(dist, 0);
        ArrayList<ArrayList<Integer>> distList = perm.getResult();  // 순열 리스트

        // 취약 지점의 각 위치를 출발점으로 설정
        for (int start = 0; start < weak.length; start++) {
            // 친구 이동 거리의 순열을 하나씩 테스트
            for (int i = 0; i < distList.size(); i++) {
                int cnt = 1;    // 사용한 친구 수 (처음엔 1명으로 시작)
                // 첫 번째 친구가 도달할 수 있는 마지막 위치 계산
                int position = weakList.get(start) + distList.get(i).get(cnt - 1);
                // 취약 지점들 하나씩 확인
                for (int index = start; index < start + weak.length; index++) {
                    // 현재 친구가 도달할 수 없는 취약 지점이 나타나면
                    if(position < weakList.get(index)) {
                        cnt += 1;   // 새로운 친구 추가
                        // 친구 수가 부족하면 종료
                        if (cnt > dist.length) {
                            break;
                        }
                        // 새로운 친구가 도달할 수 있는 마지막 위치 갱신
                        position = weakList.get(index) + distList.get(i).get(cnt - 1);
                    }
                }
                // 최소 인원 갱신
                answer = Math.min(answer, cnt);
            }
        }
        // 모든 경우 확인한 후, 친구가 부족하면 -1 반환
        if (answer > dist.length) {
            return -1;
        }
        // 최소 인원 반환
        return answer;
    }
}