(javascript) 자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059?language=javascript

프로그래머스

 

 열쇠를 돌려가며 자물쇠에 끼우는 문제

 n과 m의 크기가 작으므로 무식하게 풀기로 했다

 

 자물쇠의 크기를 n*n, 열쇠의 크기를 m*m이라고 할 때, 열쇠를 1-m, 1-m부터 n, n까지 미끄러트리면서 자물쇠가 풀리는지 확인한다. 자물쇠를 푸는데 열쇠가 모두 들어갈 필요는 없기 때문이다.

 따라서 먼저 두개의 for문으로 감싸준다.

const n = lock.length;
const m = key.length;
for (let i = 1 - m; i < n; i++) {
    for (let j = 1 - m; j < n; j++) {
    	// ...
    }
}

 

 그 다음은 해당 위치에서 열쇠로 자물쇠를 풀 수 있는지 확인해준다.

 자물쇠를 풀려면 자물쇠의 모든 칸이 채워져야한다. 따라서 자물쇠의 모든 칸이 1인지, 그리고 해당 칸에 열쇠가 있는지, 있다면 열쇠가 1인지 확인해준다.

 현재 위치 col = [1, n), row = [1, n)일 때, 자물쇠가 1인지 확인하는 변수 t1 = lock[col][row]이다.

 마찬가지로 해당 칸에 열쇠가 1인지 확인해주는 변수 t2를 설정한 뒤, 열쇠가 1인지 확인해준다.

 

 자물쇠를 풀려면 해당 칸에 자물쇠나 열쇠 둘 중 하나가 1이어야한다. 그러므로 t1 + t2를 계산해서 그 값이 1인지 확인해준다.

 만약 열쇠와 자물쇠가 맞물리지 않는 부분이 있다면 열쇠를 한칸 움직여서 처음부터 다시 시도한다.

 

 열쇠와 자물쇠가 맞는지 확인하는 부분을 만들었으니 열쇠를 돌려서 테스트해야한다.

 열쇠를 돌리기 위한 함수 rotate를 정의했다.

 

 전체 코드의 시간복잡도는 O(N^4)로 상당히 크다. 하지만 주어진 n, m의 크기가 20으로 매우 작기 때문에 여유롭게 통과했다.

코드

function solution(key, lock) {
    // 열쇠 회전
    let key_90 = rotate(key);
    let key_180 = rotate(key_90);
    let key_270 = rotate(key_180);
    const keys = [key, key_90, key_180, key_270];

    // 정방향
    const n = lock.length;
    const m = key.length;
    for (let i = 1 - m; i < n; i++) {
        for (let j = 1 - m; j < n; j++) {
            // 열쇠 맞대어보기
            loop: for (var k = 0; k < 4; k++) {
                const key_n = keys[k];
                for (let col = 0; col < n; col++) {
                    for (let row = 0; row < n; row++) {
                        let t1 = lock[col][row];
                        let t2 = 0;
                        if (col - i >= 0 && col - i < m && row - j >= 0 && row - j < m)
                            t2 = key_n[col - i][row - j];
                        if (t1 + t2 !== 1)
                            continue loop;
                    }
                }
                return true;
            }
        }
    }
    return false;
}

function rotate(key) {
    let m = key.length;
    let result = Array.from({ length: m }, () => new Array(m));
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < m; j++) {
            result[j][m - i - 1] = key[i][j];
        }
    }
    return result;
}