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

[자물쇠와 열쇠]

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

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

 

* 조건

1. 키(M*M)와 자물쇠(N*N)가 2차원 배열로 존재한다
2. 배열에서 값 1은 돌기이고, 값 0은 홈이다
3. 주어진 키를 가지고(돌기) 자물쇠의 돌기 부분과 겹치지 않으면서 홈 부분에 넣을 수 있다면 true
4. 키는 90도(시계 방향)으로 회전하여 자물쇠를 열어볼 수 있다

* 알고리즘

- 주어진 키를 통해 자물쇠를 열 수 있는지 모든 경우의 수 탐색: 브루트포스

 

* 로직(Logic)

- 자물쇠 배열 사이즈를 벗어난 상태에서도 키의 돌기 부분과 맞춰볼 수 있기 때문에 최대 허용 사이즈 20*20으로 늘려놨다고 가정한다 (실제로 늘리는 것은 아님)

- 가장 처음 lock과 key를 매칭 시킬 수 있는 부분은 lock 맵의 (0,0) 칸이다.

- 이를 고려해 왼쪽 위 대각선으로 key 사이즈만큼 늘려놓으면 기존에 적용한 최대 허용 사이즈로 인해 낭비되는 부분을 조금이나마 줄일 수 있다.

- 가상 배열의 좌측 상단부터 기준점을 잡고 키를 홈에 넣을 수 있는지 여부를 파악한다

- 넣을 수 있는 횟수와 자물쇠 홈의 개수가 같고 && 키가 자물쇠의 돌기에 부딪히지 않는다면 -> 열수 있다(true)

 

- 키 배열을 90도 회전시키면서 위 과정을 반복한다

 

//개선 전 코드

public class Problem_Key {

    static int[][] keyMap;
    static int keySize;
    static int lockSize;
    static int cnt_lock = 0;

    public static void main(String[] args) {
        int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
        int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        boolean ans = solution(key, lock);
        System.out.println(ans);
    }

    public static boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        lockSize = lock.length;
        keySize = key.length;
        keyMap = new int[keySize][keySize];

        for(int i=0; i<lockSize; ++i){
            for(int j=0; j<lockSize; ++j){
                if(lock[i][j] == 0) cnt_lock++;
            }
        }

        //key 값 복사
        for(int i=0; i<key.length; ++i){
            for(int j=0; j<key.length; ++j){
                keyMap[i][j] = key[i][j];
            }
        }

        for(int i=0; i<4; ++i){
            //key 회전
            keyMap = rotateKey();

            for(int y=-20; y<=20; ++y){
                for(int x=-20; x<=20; ++x){
                    if(openLock(y, x, lock)){
                        answer = true;
                        return answer;
                    }
                }
            }
        }

        return answer;
    }

    //시계 방향으로 회전
    private static int[][] rotateKey() {
        int[][] tmp = new int[keySize][keySize];
        for(int i = 0; i< keySize; ++i){
            for(int j = 0; j< keySize; ++j){
                tmp[i][j] = keyMap[keySize-1-j][i];
            }
        }
        return tmp;
    }

    private static boolean openLock(int y, int x, int[][] lock) {
        boolean check = true;
        int cnt = 0;
        for(int i=0; i<keySize; ++i){
            for(int j=0; j<keySize; ++j){
                int moveY = y + i;
                int moveX = x + j;
                if(isRanged(moveY, moveX)){
                    if(keyMap[i][j] == 1 && lock[moveY][moveX] == 0){
                        cnt++;
                    }
                    else if(keyMap[i][j] == 1 && lock[moveY][moveX] == 1) {
                        return false;
                    }
                }
            }
        }
        if(check && (cnt == cnt_lock)) return true;

        return false;
    }

    private static boolean isRanged(int y, int x) {
        if(y>=0 && y<lockSize && x>=0 && x<lockSize) return true;
        return false;
    }
}

 

//개선 후 코드

public class Problem_LockAndKey {

    static int M;   //key 사이즈
    static int N;   //lock 사이즈

    static int count_Lock = 0;

    public static void main(String[] args) {
        int[][] key = {
                {0, 0, 0}, {1, 0, 0}, {0, 1, 1}
        };

        int[][] lock = {
                {1, 1, 1}, {1, 1, 0}, {1, 0, 1}
        };
        boolean answer = solution(key, lock);
        System.out.println(answer);
    }

    public static boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        M = key.length;
        N = lock.length;

        //lock의 홈 부분 개수 파악
        for(int i=0; i<lock.length; ++i){
            for(int j=0; j<lock.length; ++j){
                if(lock[i][j] == 0) count_Lock++;
            }
        }

        //key 시계방향 90도 회전 (회전은 총 4번)
        for(int r=0; r<4; ++r){
            key = doRotate(key);

            //lock을 풀 수 있는지 판단
            //(key 사이즈 - 1)*2 만큼 사이즈를 확장해야 모든 범위에서 측정 가능
            int size = M-1;
            for(int i= (-size); i<N; ++i){
                for(int j= (-size); j<N; ++j){
                    if(openLock(key, lock, i, j)){
                        return true;
                    }
                }
            }
        }

        return answer;
    }

    private static boolean openLock(int[][] key, int[][] lock, int row, int col) {
        //해당 좌표를 기준으로 key size만큼 계속 확인
        int cnt = 0;
        for(int i=0; i<M; ++i){
            int moveY = row + i;
            for(int j=0; j<M; ++j){
                int moveX = col + j;

                //lock 맵에 속하면서 key가 잘 맞는지 확인
                if(isRanged(moveY, moveX)){
                    if(key[i][j] == 1 && lock[moveY][moveX] == 0) cnt++;
                    else if(key[i][j] == 1 && lock[moveY][moveX] == 1) return false;
                }
            }
        }

        if(cnt != count_Lock) return false;
        return true;
    }

    private static boolean isRanged(int y, int x) {
        if(y >=0 && y<N && x>=0 && x<N) return true;
        return false;
    }

    private static int[][] doRotate(int[][] key) {
        int[][] tmp = new int[M][M];
        for(int i=0; i<M; ++i){
            for(int j=0; j<M; ++j){
                tmp[i][j] = key[M-1-j][i];
            }
        }
        return tmp;
    }
}

 

배열 사이즈를 확장시킬 때 꼭 만들지 않고 가상으로 처리하는 방법을 몰라서 애를 썼던거 같다. 이렇게 가상으로 적용시키는 방식도 고려해봐야겠다.