이코테 0807 - 구현 기출문제4)

📚 외벽 점검

• weak과 dist 모두 범위가 크지 않음, 모든 경우를 구해야하는 완전탐색 문제

• 1. 모든 weak 케이스 만들기
     n=12, weak = [1,5,6,10] 일 때 나올 수 있는 모든 경우는
     [1,5,6,10], [5,6,10,13], [6,10,13,17], [10,13,17,18] 이 된다.
     원형큐의 rotate 처럼 맨 앞 원소가 뒤에 추가 되는 식이고, 각 위치차를 쉽게 계산하기 위해 n값을 더해준다.
• 2. 모든 dist 케이스 만들기
     순열 이용
• 3. 모든 weak 케이스에 대해 모든 dist 케이스 검사
     : 예를 들어 [1,3,4,9,10]의 weak과 [3,5,7]의 dist를 이용하여 탐색한다고 가정하면, 1번 지점에서 3짜리 dist가 사용된다. 1+3 = 4이므로, 3,4번 지점은 한번에 체크가 된다(check 메소드). 그럼 다음 출발지는 9번 지점이 되고, 여기서 5짜리 dist가 사용된다. 9+5 = 14이므로, 10번 지점까지 한번에 체크가 된다. 이렇게 되면 2개의 dist값만 사용하고 모두 탐색이 진행된 것이다.

(행복유치원 문제와 같은 원리인 줄 알았는데 아니었다..)

// 외벽점검(완전탐색)
// 주의) 외벽의 길이(n)는 12가 아님. 1~200 범위다

package ThisIsCodingTest;

public class Java0807_1 {
	
	public int[] weak,dist;
	public int[][] weakAllCase;
	public int n,answer;
	
    public int solution(int n, int[] weak, int[] dist) {
    	
    	weakAllCase = new int[weak.length][weak.length];
    	
    	this.weak = weak;
    	this.dist = dist;
    	this.answer = dist.length + 1; // Math.min을 위한 초기화
    	this.n=n;
    	
    	//	weak의 모든 케이스 구하기
    	makeWeakAllCase(); 		
    	
    	// dist의 모든 케이스 구하기(DFS)
    	makeDistAllCase(new boolean[dist.length],new int[dist.length],0);
    	
    	
        
        return answer==dist.length+1 ? -1:answer;
    }

	private void makeDistAllCase(boolean[] visited, int[] distCase, int idx) {
		
		if(idx == dist.length) {
			for(int[] weakCase:weakAllCase)
				check(distCase,weakCase);
		}
		
		for(int i=0;i<dist.length;i++) {
			if(!visited[i]) {
				visited[i] = true;
				distCase[idx] = dist[i]; // 원소 할당
				
				makeDistAllCase(visited, distCase, idx+1);
				visited[i]=false;
				distCase[idx]=0; // 다시 빼기
				
			}
		}
		
	}

	private void check(int[] distCase, int[] weakCase) {
		
		int currentWeakIdx =0;
		int nextWeakIdx=0;
		int distIdx =0;
		
		while(currentWeakIdx<weakCase.length&& distIdx<distCase.length) {
			
			nextWeakIdx = currentWeakIdx+1;
			while(nextWeakIdx<weakCase.length&&
					weakCase[currentWeakIdx]+distCase[distIdx]>=weakCase[nextWeakIdx])
				nextWeakIdx++;
			
			currentWeakIdx = nextWeakIdx;
			distIdx++;
		}
		
		if(currentWeakIdx == weakCase.length)
			answer = Math.min(answer, distIdx);
		
	}

	private void makeWeakAllCase() {
		
		int[] weakCase = this.weak.clone();
		weakAllCase[0] = weakCase.clone(); // 맨처음 케이스는 원본 배열
		
		// 원형 큐의 rotate방식으로 각 케이스 셍성
		for(int i=1;i<weak.length;i++) {
			int temp = weakCase[0]; 	// 맨뒤로 이동 할 맨 앞 원소
			
			// 나머지 원소는 한 칸씩 앞으로 떙기기
			for(int j=1;j<weak.length;j++)
				weakCase[j-1] = weakCase[j];
			
			// 위치차 계산을 쉽게 하기위해 맨뒤로 이동한 원소는 +n
			weakCase[weak.length-1] = temp+n;
			
			weakAllCase[i] = weakCase.clone();
		}
		
	}
}