2020카카오공채 : 자물쇠와 열쇠

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열 수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수) 크기 2차원 배열입니다.

• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.

• M은 항상 N 이하입니다.

• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.

  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다

 

해결

1. 문제를 해결하기전에 필요한 메서드를 정리한다.

 

1. 열쇠를 맞추기 위해 회전시키는 "spin" 메서드.

2. 열쇠를 맞추기 위해 움직이는 "move" 메서드

3. "spin"과 "move" 후에 열쇠를 자물쇠에 맞추는 "match" 메서드

4. 열쇠가 자물쇠에 일치하는지 검사하는 "isUnlock" 메서드.

 

2. 해당 문제는 "solution" 메서드에 정수형 2차원 배열인 "key"와 "lock"이 파라미터로 주어진다.

 

간단히 생각해보면 정사각형 모양의 배열임으로 4번의 회전 후에는 원래의 모습으로 돌아온다.

public boolean solution(int[][] key, int[][] lock) {
    boolean answer = false;
    for (int i = 0; i < 4; i++) {
        if (match(key, lock)) return true;
        key = spin(key);
    }
    return answer;
}

answer에 기본값으로 false를 준 뒤, match메서드에서 구멍에 맞으면 true를 반환하도록 코딩할 것이다.

4번의 회전 (for문) 뒤에는 정답이 없는 것으로 간주. false를 반환한다.

 

 

3. "spin" 메서드 구현

 

2차원 배열을 회전시키는 방법은 시계방향, 반시계 방향 2가지다. 이번 문제에서는 시계방향으로 회전한다.

 private int[][] spin(int[][] arr) {
    int[][] temp = new int[arr.length][arr.length];
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            temp[i][j] = arr[arr.length - 1 - j][i];
        }
    }
    return temp;
}

회전된 배열의 값을 저장할 temp배열을 선언해주고 arr배열이 시계방향으로 회전된 값을 저장해 준다.

5열의 temp [i][j] = arr [arr.length- j - 1][i]; 부분이 핵심이다.

i와 j를 뒤집어주고, 피 회전 배열의 가로의 역순(length-j) -1을 세로에 대입해준다.

이러한 작업 뒤에 temp는 arr배열이 시계방향으로 회전된 값이 저장되었다.

 

 

4. 회전에 따른 4번의 "match"메서드 호출.

 

match 메서드를 작성하기 위해서 "M은 항상 N 이하입니다."를 생각한다. 자물쇠보다 열쇠가 작을 수 있다는 소리다.

key와 lock를 파라미터로 받고 열쇠로 자물쇠의 처음부터 끝까지 훑으며 검사한다.

private boolean match(int[][] key, int[][] lock) {
    for (int i = (1 - key.length); i < lock.length; i++) {
        for (int j = (1 - key.length); j < lock.length; j++) {
            int[][] temp = move(key, lock.length, i, j);
            if (isUnlock(temp, lock)) {
                return true;
            }
        }
    }
    return false;
}

이 메서드에서 유의해야 할 점은 2, 3열에 포문 안의 i, j의 값이다.

(1 - key.length)를 시작 값을 주었는데. 이는 키가 자물쇠의 끝부분을 넘어서 걸쳐서 들어갈 수 도 있기 때문이다.

즉 모든 경우의 수를 검사해 주는 부분이다. 모든 부분을 "move"메서드를 이용해 이동하며 자물쇠가 열릴 수 있는지 "isUnlock" 메서드를 이용해 체크해준다.

 

 

5. "move" 메소드 구현

 

move 메서드는 key, lock의 길이, 이동할 행, 열의 크기를 파라미터로 받는다.

private int[][] move(int[][] key, int length, int row, int col) {
    int[][] temp = new int[length][length];
    for (int i = 0; i < key.length; i++) {
        for (int j = 0; j < key.length; j++) {
            if (i + row >= 0 && i + row < length && j + col >= 0 && j + col < length) {
                temp[i + row][j + col] = key[i][j];
            }
        }
    }
    return temp;
}

이동할 행, 열의 크기(row, col)만큼 이동해준다. 여기서 유의해야 할 점은 5번째 줄이다.

인덱스 값이 0 미만, lock의 길이 초과범위를 넘어가지 않게 경곗값을 설정해준다.

이러지 않으면 arrayindexoutofboundsexception 오류와 만나게 된다.

 

6. 마지막 "isUnlock"메서드

 

spin과 move메서드를 이용해 키값에 변화를 줬다면 이제 변화된 키값으로 자물쇠를 열어야 한다.

private boolean isUnlock(int[][] key, int[][] lock) {
    for (int i = 0; i < lock.length; i++) {
        for (int j = 0; j < lock.length; j++) {
            if ((key[i][j] + lock[i][j]) != 1) {
                return false;
            }
        }
    }
    return true;
}

간단하다.

서로 겹쳤을 시 모난 부분의 충돌과, 빈칸이 남지 않으면 된다. 예를 들면

0 0 1    1 1 0

0 1 0    1 0 1

0 1 0    1 0 1

인 경우 합을 했을 때 모든 값이 1이 됨으로 자물쇠를 열 수 있다.

4번째 줄의 if문을 통해 확인해준다.

 

전체 코드

class Solution {
    
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;

        for (int i = 0; i < 4; i++) {
            if (match(key, lock)) return true;
            key = spin(key);
        }

        return answer;
    }
    
    private int[][] spin(int[][] arr) {
        int[][] temp = new int[arr.length][arr.length];

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

        return temp;
    }

    private int[][] move(int[][] key, int length, int row, int col) {
        int[][] temp = new int[length][length];

        for (int i = 0; i < key.length; i++) {
            for (int j = 0; j < key.length; j++) {
                if (i + row >= 0 && i + row < length && j + col >= 0 && j + col < length) {
                    temp[i + row][j + col] = key[i][j];
                }
            }
        }

        return temp;
    }

    private boolean isUnlock(int[][] key, int[][] lock) {
        for (int i = 0; i < lock.length; i++) {
            for (int j = 0; j < lock.length; j++) {
                if ((key[i][j] + lock[i][j]) != 1) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean match(int[][] key, int[][] lock) {
        for (int i = (1 - key.length); i < lock.length; i++) {
            for (int j = (1 - key.length); j < lock.length; j++) {
                int[][] temp = move(key, lock.length, i, j);
                if (isUnlock(temp, lock)) {
                    return true;
                }
            }
        }
        return false;
    }
    
}

 

셀프 코드리뷰

level 3의 보통 난이도의 문제였지만 조금 어렵게 느껴졌다.

처음에 제한 사항을 제대로 확인하지 못해 시간을 좀 헤매었고. 제한시간을 맞추려 날 코딩한 기분이다.

"match" 메서드가 가장 아쉽다. 전부 다 훑는 방법보단. 키포인트를 하나 정해 서로 매치시켜서 검사하는 식으로 짰으면 어땠을까 한다.