프로그래머스_자물쇠와 열쇠_자바

 

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

코딩테스트 연습 - 자물쇠와 열쇠

열쇠의 크기는 항상 자물쇠의 크기보다 작다.

문제를 이해하는 데 있어서 중요한 점은 열쇠는 자물쇠의 범위 밖으로 나가도 된다.

 

풀이

열쇠는 이동과 회전을 할 수 있다. 

1. 열쇠가 이동하는 경우

예를 들어 열쇠가 3 * 3 배열이고 자물쇠가 2 * 2 배열이라면 

열쇠가 자물쇠의 맨 왼쪽 위부터 오른쪽 아래까지 이동시키면서 겹치는 모든 경우를 검사하여 정답인 경우(자물쇠가 열쇠와 겹치는 부분의 합(돌기: 1 홈 : 0) 이 모두 1인 경우) 찾아내면 된다. 

 

2. 열쇠가 회전하는 경우

 

열쇠가 회전하는 경우는 열쇠가 이동할 때마다 회전을 시켜 검사해주면 된다. 

90회 전하는 경우 코드이다.

	for(int i = 0; i < arr.length; i++) {
    		for(int j = 0; j < arr.length; j++) {
    				newArr[j][arr.length - 1 - i] = arr[i][j];
    		}
    	}

위 두 가지를 생각하면서 구현을 하면 정답을 구할 수 있다.

주의해야 할 예외가 있다면 자물쇠가 애초에 열려있는 경우는 검사할 필요 없이 true를 리턴해주면 된다.

다음은 전체 코드이다.

 

class Solution {
    static int[][] keyArr;
	static int[][] lockArr;
    public static boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        keyArr = key;
        lockArr = lock;
        
         
        for(int i = 0; i < lock.length + key.length - 1; i++) {
        	for(int j = 0; j < lock.length + key.length - 1; j++) {
        		// 회전 	
        		for(int k = 0; k < 4; k++) {
        	   		
        			int[][] rotateedArr = rotate(key, k, 0);
        			int[][] bigArr = makeBigArr();
        			if(isFinish(bigArr)) return true;
        			int[][] sumArr = sumArr(rotateedArr, bigArr, i, j);
        			if(isFinish(sumArr)) return true;
        			// key배열을 회전시킨다. 
        			// bigArr 과 합쳐준다.
        			// 끝난는지 검사한다. 
        		}
        	}
        }
        return false;
 }
    
    public static int[][] sumArr(int[][] rotatedArr, int[][] bigArr, int s, int e) {
    	
    	for(int i = 0; i <  keyArr.length; i++) {
    		
    		for(int j = 0; j <  keyArr.length; j++) {
    
    			bigArr[s + i][e + j] += rotatedArr[i][j];
    		}
    	}

    	
    	return bigArr;
    }
    
    public static int[][] rotate(int[][] arr, int d, int c){
    	
    	if(d == c) {
    		return arr;
    	}
    	int[][] newArr = new int[arr.length][arr.length];
    	
   	   	for(int i = 0; i < arr.length; i++) {
    		for(int j = 0; j < arr.length; j++) {
    				newArr[j][arr.length - 1 - i] = arr[i][j];
    		}
    	}
    	
   	   	return rotate(newArr, d, c + 1);
    }
    
    public static boolean isFinish(int[][] sumArr) {
    	
    	for(int i = 0; i < lockArr.length; i++) {
        	for(int j = 0; j < lockArr.length; j++) {
        		if(sumArr[keyArr.length - 1 + i][keyArr.length - 1 + j] != 1) {
        			return false;
        		}
        	}
        }

    	
    	return true;
    }
    
    public static int[][] makeBigArr() {
    	
    	int[][] bigArr = new int[lockArr.length + 2 * (keyArr.length - 1)][lockArr.length + 2 * (keyArr.length - 1)];
        for(int i = 0; i < lockArr.length; i++) {
        	for(int j = 0; j < lockArr.length; j++) {
        		bigArr[keyArr.length - 1 + i][keyArr.length - 1 + j] = lockArr[i][j];
        	}
        }
        
        return bigArr;
    }
    

}