[프로그래머스] 자물쇠와 열쇠 (Java)

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

문제풀이

나타날 수 있는 모든 모양의 키를 자물쇠와 대조해야하는 문제다. 따라서 모든 경우의 수를 다 구하는 것이 핵심이다.

• 키 배열의 회전
  • 키 배열이 0도, 90도, 180도, 270도로 회전하여 나타나는 모양은 단순 이동으로 모두 포함할 수 없다. 따라서 원본과 3가지 각도로 회전한 모양을 시작점으로 이동한다.
  • rotate 함수의 핵심은
    result[c][origin.length - 1 - r] = origin[r][c];
• 키 배열의 이동
  • 처음에는 정말로 키 배열을 사방으로 이동시키는 경우를 생각했다. 하지만 공간 복잡도, 시간 복잡도가 모두 크고 비효율적이였다. 또한 키와 자물쇠의 크기가 다르기 때문에 비교에도 어려움이 있다. 사실 가능한 방법인지 모르겠다...
  • 키 배열의 이동을 실제로 이동시킬 필요없이 키와 자물쇠 배열이 서로 스쳐지나가는 것 처럼 하면 키가 이동하는 것 처럼 보일 것이다.
    • 자물쇠의 [0][0] 만 겹치는 경우부터 [len - 1][len - 1]만 겹치는 경우까지 모두 해보면 된다.
    • 비교를 좀 더 쉽게 하기 위해서 자물쇠에 패딩을 추가한다. 패딩의 크기는 (키의 길이 - 1) * 2다.

실제 시험에서 이런 문제를 접하면 과연 생각해낼 수 있을까싶다. 차근 차근 아이디어를 발전시켜나가는 연습이 필요하다.

구현코드

import java.util.*;

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
    	int size = lock.length - 1;
    	
    	for(int d = 0 ; d < 4 ; ++d) {
    		int[][] rotatedKey = rotate(d, key);
    		int[][] paddedKey = padding(rotatedKey, size);
    		
    		for(int R = 0 ; R < paddedKey.length - size ; ++R) {
    			for(int C = 0 ; C < paddedKey[0].length - size ; ++C) {
    				boolean flag = true;

    				for(int r = 0 ; r < lock.length ; ++r) {
    					for(int c = 0 ; c < lock[0].length ; ++c) {
    						if(lock[r][c] == paddedKey[R + r][C + c]) flag = false;
    					}
    				}
    				
    				if(flag) return true;
    			}
    		}
    	}
    	
    	return false;
    }

    private int[][] padding(int[][] arr, int size) {
    	int[][] result = new int[arr.length + size * 2][arr[0].length + size * 2];
    	
    	for(int r = 0 ; r < arr.length ; ++r) {
    		for(int c = 0 ; c < arr[0].length ; ++c) {
    			result[r + size][c + size] = arr[r][c];
    		}
    	}

    	return result;
	}

	private int[][] rotate(int cnt, int[][] arr){
    	if(cnt == 0) return arr;
    	
    	int[][] result = null;
    	int[][] origin = copy(arr);
    	
    	for(int i = 0 ; i < cnt ; ++i) {
    		result = new int[arr.length][arr[0].length];

    		for(int r = 0 ; r < origin.length ; ++r) {
    			for(int c = 0 ; c < origin[0].length ; ++c) {
    				result[c][origin.length - 1 - r] = origin[r][c]; 
    			}
    		
    		}
    		origin = result;
    	}
    	
    	return result;
    }
    
    private int[][] copy(int[][] arr){
    	int[][] result = new int[arr.length][arr[0].length];
    	
    	for(int r = 0 ; r < arr.length ; ++r) {
    		for(int c = 0 ; c < arr[r].length ; ++c) {
    			result[r][c] = arr[r][c];
    		}
    	}
    	
    	return result;
    }
}