[2020 KAKAO BLIND RECRUITMENT][1차] 자물쇠와 열쇠 for JAVA 재업로드

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은 돌기 부분을 나타냅니다.

 

[풀이]

조심해야 할건, Key와 Lock의 크기가 다를 수 있다는 점과, 키는 자물쇠 범위를 벗어나도 lock에만 잘 껴지면 괜찮다.

 

 

위와 같이 문제를 해결할 건데, 여기서 Key와 Lock의 크기는 다르다 했고, 위 같은 배열이 나오기 위해서는

Lock의 길이 + (key의 길이 -1) * 2를 해줘야 한다. 즉 3 + 2 * 2, 키가 자물쇠 범위를 완전 벗어나지 않은 채 배열이 넓어져야 하니까 그렇다.

 

1. 키의 시작부분 정해주기

- 키가 어디까지 가야 할지에 대한 고민이다.

- 키의 시작 점 최대 좌표 범위를 빨간 줄로 그렸다. 이 범위를 넘어가면 의미가 없다.

- 이 범위는 전체 배열.length - ( key.length - 1)로 구할 수 있다.

 

2. 키 채우기

- 키의 시작부분이 정해졌으면 그 상태에서 key.length만큼 2차원 배열을 채워나가는 반복문을 작성하면 된다.

 

3. 올바른지 확인하기

- 사실 이 부분은 채우면서 비교하면 좋은데 이미 코드를 작성해버려서 나중에 시간 날 때 수정하겠다.

- 나는 이 부분을 clone을 사용했다. 바보같은 로직인데, 그냥 isCorrect 같은 함수를 만들어서 새로운 배열을 선언하고 비교하는 것이 효율적이다.

 

4. 키 바꿔주기

- 다 비교한 키는 90도 rotate를 해주어 바꿔주도록 한다.

 

[코드]

    public boolean solution(int[][] key, int[][] lock) {
        // 자물쇠 칸을 만들어야한다.
        int keyLen = key.length;
        int[][] newLock = new int[lock.length + (keyLen - 1) * 2][lock.length + (keyLen - 1) * 2];
 
        // 새로운 자물쇠 배열
        int lockIdxI = 0;
        int lockIdxj = 0;
        for (int i = keyLen - 1; i < (keyLen - 1) + lock.length; i++) {
            lockIdxj = 0;
            for (int j = keyLen - 1; j < (keyLen - 1) + lock.length; j++) {
                newLock[i][j] = lock[lockIdxI][lockIdxj++];
            }
            lockIdxI++;
        }
        
        
        for (int i = 0; i < 4; i++) {                                            //3번의 키회전에 대해
            int[][] tempNewLock = new int[newLock.length][newLock.length];
            for (int q = 0; q < newLock.length - (keyLen - 1); q++) {             // 하나의 키에 대해서 시작지점일 뿐
 
                for (int w = 0; w < newLock.length - (keyLen - 1); w++) {         // x,y좌표가 결정됨.
                    for (int k = 0; k < tempNewLock.length; k++) {                  // 새로운 tempNewLock
                        tempNewLock[k] = newLock[k].clone();
                    }
                    int tempIdxI = 0;
                    int tempIdxJ = 0;
                    for (int r = q; r < q + key.length; r++) {                     // key채우는 로직
                        for (int z = w; z < w + key.length; z++) {
                            tempNewLock[r][z] += key[tempIdxI][tempIdxJ++];
                        }
                        tempIdxI++;
                        tempIdxJ = 0;
                    }
 
                    // 자물쇠에 키가 맞는지
                    lockIdxI = 0;
                    lockIdxj = 0;
                    boolean check = true;
                    for (int c = keyLen - 1; c < (keyLen - 1) + lock.length; c++) {
                        lockIdxj = 0;
                        for (int h = keyLen - 1; h < (keyLen - 1) + lock.length; h++) {
                            if (tempNewLock[c][h] > 1 || tempNewLock[c][h] == 0) {            //중간에 맞지 않는 곳이거나 비어있는 곳이 있으면 false
                                check = false;
                                break;
                            }
                        }
                        if (!check) {                                                        //false면 break;
                            break;
                        }
                    }
                    if (check) {                                                            //check가 true가 되어 나온다면 일치한다는 뜻이므로 true
                        return true;
                    }
                }
            }
 
            key = getRotate(key);                                                            //키회전
            if (i == 3) {                                                                    //마지막이면
                return false;
            }
        }
        return false;
    }
 
 
    public int[][] getRotate(int[][] arr) {
        int[][] newKey = new int[arr.length][arr.length];
        for (int i = 0; i < newKey.length; i++) {
            int tempIdx = newKey.length - 1;
            for (int j = 0; j < newKey.length; j++) {
                newKey[i][j] = arr[tempIdx--][i];
            }
        }
        return newKey;
    }

테스트 케이스 통과

느낀 점: 저번과는 다르게 혼자 생각하고 판단하며 작성했다. 시간도 좀 걸려서 아쉽고, 코드도 수정하고 싶은데 나중에 잊힐 때쯤 다시 풀어보는 것이 좋을 것 같다고 판단했다. 마무리해야겠다.