프로그래머스 | 자물쇠와 열쇠 - java

프로그래머스

 

# 핵심

2차원 배열을 어떻게 90도 회전시킬까?

 

이차원 배열을 90도 회전시키는 방법!!!

 

 

이러한 문제를 깡구현 문제라고 하나? 이차원 배열을 시계방향으로 90도 돌려보면서 빈칸에 맞는지 싹 훑어보는 방식으로 진행된다.

 

Key의 크기가 Lock의 크기보다 작거나 같기 때문에, Lock에 패딩을 덧씌운 다음에 왼쪽 위부터 오른쪽 아래까지 Key를 싹 훑으면서 조건이 맞는다면 true를 리턴시키면 된다. 만약 조건이 맞지 않는다면 key를 90도 회전시킨 다음에 다시 시도해보면 된다. 이것 마치 컨볼루션

 

개념은 어렵지 않지만 이를 막상 구현하려고 하면 그렇게 만만하게 되지는 않는다. 필터(Key) 크기를 잘 맞추기 위해 패딩을 덧씌워 놨으므로 인덱스를 잘 잡는것도 중요하고, 또 중요한게 이차원 배열을 어떻게 90도로 회전시키는지?이다

 

그리고 이차원 배열을 90도로 회전시키는데 진짜 기똥찬 방법이 있다.

x=y 축 기준으로 뒤집은 다음에 x축으로 한번 더 뒤집으면 바로 시계방향 90도 회전한 결과와 같아진다.

엄청난 발견! 이거 발견하고 정말 소름돋았다

 

    private void rotate(int[][] board, int n) {
        int tmp;
        // (1) x=y축 뒤집기 
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(j == n - i - 1) break;
                tmp = board[i][j];
                board[i][j] = board[n - j - 1][n - i - 1];
                board[n - j - 1][n - i - 1] = tmp;
            }
        }
        // (2) x축 뒤집기
        for(int i = 0; i < n / 2; i++) {
            for(int j = 0; j < n; j++) {
                tmp = board[n - i - 1][j];
                board[n - i - 1][j] = board[i][j];
                board[i][j] = tmp;
            }
        }
    }

 

이 방법이 이중 반복문을 두번 돌아야하고 조금 번거로울 수도 있다.

이거 말고도 그냥 인덱스를 이용해 깡으로 회전시키는 방법이 있는데 그것도 꽤 만만하지 않고 머리아픈 방법이다.. 그런 법칙 찾는게 은근 까다롭다

 

 

아주 잘 돌아가는 것을 확인할 수 있다 :D

 

 

걍 대충 이런 느낌이다

패딩을 포함한 이차원 배열의 총 길이는 N + 2M - 2

패딩을 제외한 알맹이 부분은 (M-1, M-1) 부터 시작!

 

# 통과 코드

import java.util.*;

class Solution {

    private void rotate(int[][] lock) {
        // x=y 축으로 뒤집고 -> x축으로 한번 더 뒤집는다
        int tmp;
        for(int i = 0; i < lock.length; i++) {
            for(int j = 0; j < lock.length; j++) {
                if(j == lock.length - i - 1) break;
                tmp = lock[i][j];
                lock[i][j] = lock[lock.length - j - 1][lock.length - i - 1];
                lock[lock.length - j - 1][lock.length - i - 1] = tmp;
            }
        }
        for(int i = 0; i < lock.length / 2; i++) {
            for(int j = 0; j < lock.length; j++) {
                tmp = lock[lock.length - 1 - i][j];
                lock[lock.length - 1 - i][j] = lock[i][j];
                lock[i][j] = tmp;
            }
        }
    }

    public boolean solution(int[][] key, int[][] lock) {
        int N = lock.length;
        int M = key.length;
        int[][] board = new int[N + 2 * M - 2][N + 2 * M - 2]; // padding 포함

        // init
        for (int[] ints : board) {
            Arrays.fill(ints, 2); // padding
        }
        for(int idx_i = M - 1, i = 0; i < N; i++, idx_i++) {
            for(int idx_j = M - 1, j = 0; j < N; j++, idx_j++) {
                board[idx_i][idx_j] = lock[i][j];
            }
        }

        // conv
        for(int rotate = 0; rotate < 4; rotate++) {
            boolean flag = false;
            for(int idx_i = 0; idx_i < N + M - 1; idx_i++) {
                for(int idx_j = 0; idx_j < N + M - 1; idx_j++) {
                    // sliding
                    for(int i = 0; i < M; i++) {
                        for(int j = 0; j < M; j++) {
                            // 열쇠의 돌기와 자물쇠의 홈이 겹치면 안된다
                            if(board[idx_i + i][idx_j + j] == 1 && key[i][j] == 1) break;
                            // 겹치는 부분 체크
                            if(board[idx_i + i][idx_j + j] == 0 && key[i][j] == 1) {
                                board[idx_i + i][idx_j + j] = 2;
                            }
                        }
                    }

                    // check
                    flag = false;
                    for(int i = M - 1; i < N + M - 1; i++) {
                        for(int j = M - 1; j < N + M - 1; j++) {
                            // 채워지지 않은 부분이 있다면 break
                            if(board[i][j] == 0) {
                                flag = true; 
                                break;
                            }
                        }
                        if(flag) break;
                    }
                    // 모든 자물쇠 홈이 채워졌다면 true 
                    if(!flag) return true;

                    // reset
                    for(int i = M - 1; i < N + M - 1; i++) {
                        for(int j = M - 1; j < N + M - 1; j++) {
                            if(board[i][j] == 2) {
                                board[i][j] = 0;
                            }
                        }
                    }
                }
            }
            rotate(key);
        }
        return false;
    }
}

만든 코드가 짧지는 않은 것 같다. 

나중에 다른 사람들의 코드를 좀 참고해서 리팩토링을 한번 해봐야겠다.