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

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

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

1. 유형

구현

 

2. 시뮬레이션

 

1. 한점을 선택

2. 가장 먼 곳을 탐색할 수 있는 사람부터 사용

3. 모든 weak를 탐색할 수 있을때까지 위를 반복

 

위 처럼 시뮬레이션을 돌리면, 

• 가장 먼저 1을 선택 후, 2가지 경우의 수가 나온다.
  
  • 9 선택하는 경우 -> 5만큼 탐색하면 모든 weak탐색가능 ->2명 필요
  • 10 선택하는 경우 -> 5만큼 탐색해도 9번은 아직 탐색 못했음 -> 다시 9번을 탐색 -> 3명 필요

위와 같은 형식으로 완전탐색을 해야한다. 정답은 10번에서 7만큼 이동시 1명으로 전부 weak를 탐색가능.

 

3. 코드

import java.util.*;

class Solution {
	static int N, INF = 987654321, min;
	static int[] Weak;
	static int[] Dist;

	public int solution(int n, int[] weak, int[] dist) {
		int answer = 0;
		min = INF;
		N = n;
		Weak = weak;
		Arrays.sort(dist);
		Dist = dist;
		for (int i = 0; i < weak.length; i++) {
			permutaion(1, i, new boolean[weak.length]);
		}

		answer = min == INF ? -1 : min;
		return answer;
	}

	static void permutaion(int depth, int pos, boolean visit[]) {
		if (depth > Dist.length)
			return;
		if (min <= depth)
			return;
		boolean[] copyVisit = Arrays.copyOf(visit, visit.length);
		for (int i = 0; i < Weak.length; i++) {
			int nextPos = (pos + i) % Weak.length;
			int diff = nextPos >= pos ? Weak[nextPos] - Weak[pos] : Weak[nextPos] + N - Weak[pos];
			if (diff <= Dist[Dist.length - depth]) {
				copyVisit[nextPos] = true;
			} else
				break;
		}
		if (isValid(copyVisit)) {
			min = Math.min(min, depth);
			return;
		}
		for (int i = 0; i < Weak.length; i++) {
			if (!copyVisit[i])
				permutaion(depth + 1, i, copyVisit);
		}
	}

	static boolean isValid(boolean visit[]) {
		for (int i = 0; i < visit.length; i++) {
			if (!visit[i])
				return false;
		}
		return true;
	}
}