[프로그래머스/자바] 자물쇠와 열쇠 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

열쇠의 일부분만 사용해서 자물쇠를 열 수도 있으므로

열쇠는 (자물쇠의 크기 + 열쇠의 크기 - 1) 만큼 자유롭게 움직일 수 있어야 한다.

열쇠를 움직이며 자물쇠를 열 수 있는지 확인할 배열 board를 만든다.

배열 가운데에 lock을 두고, 상하좌우로 (열쇠의 크기 - 1) 만큼 열쇠가 이동할 수 있다. (최소 한 부분은 자물쇠와 맞물려야 하므로 -1을 해준다.)

배열의 크기는 (lock 크기 + * 2 (key 크기 + 1))가 된다.

 

 

board 배열의 가운데에 lock을 더해준다.

key를 회전해가며 board에 더해주고 lock 위치가 모두 1인지 확인한다.

이때 key를 board에 더해줄 때 board[][] = key[][]가 아닌 board[][] += key[][]를 해줘야 한다.

이유는 문제에 열쇠의 돌기와 자물쇠의 돌기가 만나면 안된다고 적혀있으므로,

돌기끼리 만나 2인 경우도 자물쇠가 맞춰지지 않은 경우로 생각해야 한다.

 

모두 1인 경우 자물쇠가 맞춰진 경우이므로 true를 반환하고,

모든 경우를 고려할 때까지 자물쇠가 맞춰진 경우가 없다면 false를 반환한다. 

 

 

key를 회전할 때는 

가장 첫번째 열이 마지막 행으로 가고,

두번째 열이 마지막에서 두번째 행으로 가는 규칙을 이용해 for문을 작성했다.

 

 

 

배운점 및 느낀점

처음에 2차원 배열 깊은 복사를 하기 위해 그냥 배열명.clone()을 사용했는데,

디버깅 해보니까 배열을 합칠 때 계속 누적되어서 큰 값이 저장되어 있었다.

생각해보니 2차원 배열은 clone 한번으로 깊은 복사가 되는게 아니라,

for문을 사용해야 했던 거다..!

그래서 for문으로 배열명[i].clone()으로 코드를 수정해 해결했다.

너무 당연하고 중요한 걸 착각하다니.. 

 

그리고 2020 코테 Level 3 문제 중 가장 정답률이 높은 걸로 알고 있는데,

나한텐 Level 3 문제 중에서 제일 어려웠다.

https://www.youtube.com/watch?v=I1App3qLi6o&t=547s 

어떻게 풀어야할지 감이 안잡혀서 이 영상 앞부분의 문제 설명만 참고해서 코드를 작성했다.

구현하는 건 좀 까다롭지만 어렵지 않았는데,

접근 방식을 떠올리는게 힘들었던 문제다.

배열의 padding..! 다음엔 꼭 스스로 떠올리고 싶다. ㅠ

 

 

class Solution {
    static int key_len;
	static int lock_len;
	static int board_len;
    
    public boolean solution(int[][] key, int[][] lock) {
        key_len = key.length;
        lock_len = lock.length;
        board_len = lock_len + 2 * (key_len - 1);
		
        // 상하좌우 key_len - 1 만큼 padding
        int[][] board = new int[board_len][board_len];
        
        // padding 한 배열의 중앙에 lock 대입
        for(int i=0;i<lock_len;i++) {
        	for(int j=0;j<lock_len;j++)
        		board[i + key_len - 1][j + key_len - 1] = lock[i][j];
        }
        
        for(int i=0;i<board_len - (key_len - 1);i++) {
        	for(int j=0;j<board_len - (key_len - 1);j++) {
    			int[][] new_key = key;
 
    			// 회전 안한 상태로 한 번 체크, 3번 회전해서 체크
        		for(int k=0;k<4;k++) {
        			if(k != 0)
        				new_key = rotate(new_key);
        			
        			int[][] new_board = boardSum(board, new_key, i, j);
        			if(check(new_board))
        				return true;
        		}
        	}
        }
        
        return false;
    }
	
	// board에 key를 합치기
	static int[][] boardSum(int[][] board, int[][] key, int x, int y) {
		int[][] new_board = new int[board_len][board_len];
		
		for(int i=0;i<board_len;i++)
			new_board[i] = board[i].clone();
		
		for(int i=0;i<key_len;i++) {
			for(int j=0;j<key_len;j++)
				new_board[x + i][y + j] += key[i][j];
		}
		
		return new_board;
	}
	
	// lock 위치가 모두 1인지 체크
	static boolean check(int[][] board) {
		for(int i=0;i<lock_len;i++) {
			for(int j=0;j<lock_len;j++)
				if(board[i + key_len - 1][j + key_len - 1] != 1)
					return false;
		}
		
		return true;
	}
	
	// 시계 방향으로 90도 회전
	static int[][] rotate(int[][] key) {
		int[][] newKey = new int[key_len][key_len];
		
		for(int i=0;i<key_len;i++) {
			int[] temp = key[i];
			for(int j=0;j<key_len;j++)
				newKey[j][key_len - 1 - i] = temp[j];
		}
		
		return newKey;
	}
}