[프로그래머스]자물쇠와 열쇠 - JAVA

[프로그래머스]자물쇠와 열쇠

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

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

풀이

특별한 알고리즘을 사용하지않는 구현, 시뮬레이션 문제이다. 그러나 어떻게 풀어야 할지 아이디어를 생각해 내기 어려웠던 문제라고 생각이 든다.

 

문제를 푸는 핵심 아이디어는 아래 와 같다.

1. lock를 확장한다.

2. key를 회전한다.

3. key가 lock에 맞는지 확인힌다.

 

하나씩 차근차근 살펴보쟝.

1. lock를 확장한다.

확장하는 이유는 키의 일부가 자물쇠의 영역을 벗어나도 키로 자물쇠를 열 수 있으면 정답이 되기 때문이다. 그럼 얼만큼 확장할 것인지 생각해 보면 lock와 key가 겹칠수 있는 모든 경우를 계산할 수 있을 만큼 확장해야 한다. 

이때 중요할 점은 키의 크기와 자물쇠의 크기는 항상 같지 않다는 조건이다.

 

문제의 예시처럼 key의 크기와 lock의 크기가 3으로 같다면 아래와 같이 확장하면 된다.

열쇠의 이동 거리를 알아보면 0,0 ~ 4,4가된다.

즉 열쇠는 가로 방향으로 5, 세로 방향으로 5만큼의 범위를 이동하게 된다. (0 ~ 4)

 

이동거리를 구하는 방법은 다음과 같다.

열쇠와 자물쇠가 처음 겹치는 부분 + 자물쇠의 크기이다. 즉, 2 + 3 = 5가 된다.

 

확장한 lock 배열을 newLock라고 부를것이다. newLock의 크기는 어떻게 되는지 생각해보면, 자물쇠의 크기 + (열쇠의 크기 - 1) * 2 = 7이 되는 것을 그림을 보면 쉽게 알 수 있다.

 

또한 확장한 newLock에도 lock에 대한 정보가 입력되야한다. 그 위치는 초록점으로 표시한 범위가 해당된다.

왼쪽 초록점의 위치는 key.length - 1이며 이 값을 point라는 이름으로 저장해 주었다.

 

만약 key의 크기와 lock의 크기가 다른경우(key가 2고, lock가 3인경우)라면 아래와 같이 확장될 것이다.

 

열쇠의 이동거리는 0,0 ~ 3,3이 된다.

 

newLock의 크기는 3 + (1 * 2) = 5가 된다.

 

point는 1이 된다.

 

크기가 달라도 위의 식이 다 성립이 된다. 이제 다음 조건을 생각해보자.

 

 

 

 

 

2. key를 회전한다.

key를 회전해서 자물쇠와 열쇠가 맞으면 정답으로 인정되므로 초록점 ~ 초록점까지 열쇠를 이동시키면서 매번 key를 회전시킨다. 회전은 시계방향으로 진행되며 총 4번하면 된다.

 

먼저, 회전하지 않았을 때는 key값을 그래로 newLock에 더해주면 된다. 더해주는 이유는 자물쇠 값이 0이면 홈, 1이면 돌기부분이기 때문에 자물쇠에 열쇠값을 더해주어 딱 맞았다면 그 값이 1인지만 판단해주면 되기 때문이다.

 

회전을 한 경우에는 회전 방향에 따라 더하는 key값을 달리 해줘야 한다. 

예를들어 시계방향으로 90도 회전한 경우는 다음과 같다.

 

기존의 key배열

0, 0	0, 1	0, 2
1, 0	1, 1	1, 2
2, 0	2, 1	2, 2

90도 회전 후 key배열

2, 0	1, 0	0, 0
2, 1	1, 1	0, 1
2, 2	2, 1	0, 2

0, 0 -> 0, 2의 위치로 이동했고,

1, 0 -> 0, 1로

2, 0 -> 0, 0으로 이동했다.

 

이를 식으로 생각해 보면

90도 회전 후 key[x][y] = 기존의 key[y][key의 길이-x-1]이 된다.

이와같은 규칙으로 나머지 회전 점화식도 모두 구해주면 된다

 

3. key와 lock이 맞는지 확인한다.

회전한 key와 newLock(확장한 lock)이 맞는지 확인한다. newLock에 기존의 lock와 회전한 key값의 홈, 돌기 부분 정보를 더해주었으니 newLock의 자물쇠 부분이 모두 1인지만 확인하면 된다. 1이 아니라면 자물쇠와 열쇠가 모두 홈부분이거나 돌기 부분끼리 만난 것이다.

 

 

코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int point = key.length - 1;     
        for(int x = 0; x < point + lock.length; x++) { //이동 거리는 열쇠와 자물쇠가 처음으로 겹치는 부분 + 자물쇠의 크기이다.
            for(int y = 0; y < point + lock.length; y++) {
                //key를 회전한다.
                for(int r = 0; r < 4; r++) {
                    int[][] newLock = new int[lock.length + key.length * 2][lock.length + key.length * 2]; //확장한 lock배열 생성
                    for(int i = 0; i < lock.length; i++) {
                        for(int j = 0; j < lock.length; j++) {
                            newLock[i + point][j + point] = lock[i][j]; //확장할 lock배열(arr) 초기화
                        }
                    }
                    match(newLock, key, r, x, y);  //newLock배열에 key배열을 더해준다
                    if(check(newLock, point, lock.length)) return true; //자물쇠 영역이 모두 유효한 값인지 확인
                }
            }
        }
        return false;
    }
    
    public void match(int[][] newLock, int[][] key, int rot, int x, int y) {
        int len = key.length;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(rot == 0) { //한 번도 회전하지 않았을 때
                    newLock[x + i][y + j] += key[i][j];
                } else if(rot == 1) { //시계방향으로 90도 회전한 경우
                    newLock[x + i][y + j] += key[j][len - i - 1];
                } else if(rot == 2) { //180도 >회전<한 경우 (뒤집은 거랑은 다름)
                    newLock[x + i][y + j] += key[len - i - 1][len- j - 1];
                } else { //270도 회전한 경우 == 반시계 방향으로 90도 회전한 경우
                    newLock[x + i][y + j] += key[len - j - 1][i];
                }
            }
        }
    }
    
    public boolean check(int[][] newLock, int point, int len) {
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(newLock[point + i][point + j] != 1) return false;
            }
        }
        return true;
    }
}