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

1. 문제

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

2. 풀이

참고 풀이

• https://dev-note-97.tistory.com/241

 

1. weak의 원형을 풀어서 일자 형태로 만든다.

for(int i = 0; i < weak.length; i++) {
	weakList.add(weak[i]);
	weakList.add(weak[i] + n);
}

2. 모든 dist의 케이스를 순열(Permutation)으로 만든다.

• 순열 코드 작성방법 참고
  https://velog.io/@minkang911/%EC%A1%B0%ED%95%A9-%EC%88%9C%EC%97%B4Combination-Permutation-Java

public static void permutation(int depth, int[] arr) {
	
	if(depth == distLength) {
		distList.add(arr.clone());
		return;
	}
	
	for(int i = 0; i < distLength; i++) {
		if(!distVisit[i]) {
			distVisit[i] = true;
			arr[depth] = i;
			permutation(depth+1, arr);
			distVisit[i] = false;
		}
	}
}

3. 코드

import java.util.*;

class Solution {
    int distLength;
    ArrayList<Integer> weakList = new ArrayList<>();
    ArrayList<int[]> distList = new ArrayList<>();
    boolean[] distVisit;
    
    public int solution(int n, int[] weak, int[] dist) {
        
        distLength = dist.length;
        distVisit = new boolean[distLength];
        
        int answer = distLength + 1;
        
        for(int i = 0; i < weak.length; i++){
            weakList.add(weak[i]);
            weakList.add(weak[i]+n);
        }
        Collections.sort(weakList);
        
        permutation(0, new int[distLength]);
        
        for(int start = 0; start < weak.length; start++){
            
            for(int[] distArr : distList){
                int cnt = 1;
                int lastPos = weakList.get(start) + dist[distArr[cnt - 1]];
                
                for(int j = start; j < start + weak.length; j++){
                    if(lastPos < weakList.get(j)){
                        cnt += 1;
                        if(cnt > distLength){
                            break;
                        }
                        lastPos = weakList.get(j) + dist[distArr[cnt - 1]];
                    }
                }
                answer = Math.min(answer, cnt);
            }
        }
        
        if(answer > distLength){
            return -1;
        } else{
            return answer;
        }
    }
    
    public void permutation(int depth, int[] arr){
        if(depth == distLength){
            distList.add(arr.clone());
            return;
        }
        
        for(int i = 0; i < distLength; i++){
            if(!distVisit[i]){
                distVisit[i] = true;
                arr[depth] = i;
                permutation(depth+1, arr);
                distVisit[i] = false;
            }
        }
    }
}