🔎 자물쇠와 열쇠

❓ 문제링크

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

📄 제출 코드

function solution(key, lock) {
    const k_len = key.length;
    const l_len = lock.length;
    const m_len = l_len + k_len * 2 - 2;
    const maps = Array.from(Array(m_len), () => new Array(m_len).fill(null));

    for (let i = k_len - 1; i <= m_len - k_len; i++) {
        for (let j = k_len - 1; j <= m_len - k_len; j++) {
            maps[i][j] = lock[i - k_len + 1][j - k_len + 1];
        }
    }

    for (let r = 0; r < 4; r++) {
        key = rotate(key);
        for (let i = 0; i < l_len + k_len - 1; i++) {
            for (let j = 0; j < l_len + k_len - 1; j++) {
                const newMap = maps.map((v) => v.slice());

                for (let k = 0; k < k_len; k++) {
                    for (let l = 0; l < k_len; l++) {
                        if (newMap[i + k][j + l] === 1 && key[k][l] === 1) {
                            newMap[i + k][j + l] = 2;
                        } else if (newMap[i + k][j + l] === 1 && key[k][l] === 0) {
                            newMap[i + k][j + l] = 1;
                        } else if (newMap[i + k][j + l] === 0 && key[k][l] === 1) {
                            newMap[i + k][j + l] = 1;
                        } else {
                            newMap[i + k][j + l] = 0;
                        }
                    }
                }
                if (checkAnswer(newMap, k_len, m_len)) return true;
            }
        }
    }
    return false;
}

function rotate(key) {
    const m = key.length;
    const newKey = Array.from(Array(m), () => Array(m).fill(null));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < m; ++j) {
            newKey[i][j] = key[m - 1 - j][i];
        }
    }
    return newKey;
}

function checkAnswer(newMap, k_len, m_len) {
    for (let i = k_len - 1; i <= m_len - k_len; i++) {
        for (let j = k_len - 1; j <= m_len - k_len; j++) {
          if (newMap[i][j] !== 1) {
            return false;
          }
        }
    }
    return true;
}
let key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]];
let lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]];
console.log(solution(key, lock));

처음에 생각한 방법은 열쇠모양을 가지고, 모든경우를 다생각하는 방법으로 생각했다.
그래서 deg0, 90,180,270으로 4번 검사해서 중간에 맞는 경우가 있으면 true 아니면 false를 리턴한다. 회전까지는 구현했는데, map을 새로 만들어 확인하는과정에서 구현이 잘안되어 결국 다른사람의 코드를 참고하였다.

예제처럼 33의 경우라면 map의 크기는 '자물쇠길이열쇠길이-모서리수(2)' 가 된다.
m_len = l_len * k_len * 2 -2
그리고 map의 가운데에 lock을 입력한다.

1. 회전

function rotate(key) {
    const m = key.length;
    const newKey = Array.from(Array(m), () => Array(m).fill(null));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < m; ++j) {
            newKey[i][j] = key[m - 1 - j][i];
        }
    }
    return newKey;
}

👉 2. 탐색

큰 배열의 인덱스를 조작하여 key 배열과 비교.
key 배열의 길이 만큼만 큰 배열을 탐색한다.
i : 오른쪽 이동. j : 아래쪽 이동
k, l: key 배열의 길이.
[i + k]와 [j + l]를 이용하여 큰 배열의 탐색을 제한
둘 다 1이면 2대입, 둘 다 0이면 0 대입.

for (let r = 0; r < 4; r++) {
        key = rotate(key);
        for (let i = 0; i < l_len + k_len - 1; i++) {
            for (let j = 0; j < l_len + k_len - 1; j++) {
                const newMap = maps.map((v) => v.slice());

                for (let k = 0; k < k_len; k++) {
                    for (let l = 0; l < k_len; l++) {
                        if (newMap[i + k][j + l] === 1 && key[k][l] === 1) {
                            newMap[i + k][j + l] = 2;
                        } else if (newMap[i + k][j + l] === 1 && key[k][l] === 0) {
                            newMap[i + k][j + l] = 1;
                        } else if (newMap[i + k][j + l] === 0 && key[k][l] === 1) {
                            newMap[i + k][j + l] = 1;
                        } else {
                            newMap[i + k][j + l] = 0;
                        }
                    }
                }
                if (checkAnswer(newMap, k_len, m_len)) return true;
            }
        }
    }

👉 3. check

newMap에서 lock부분을 검사.
0이나 2면 false리턴

function checkAnswer(newMap, k_len, m_len) {
    for (let i = k_len - 1; i <= m_len - k_len; i++) {
        for (let j = k_len - 1; j <= m_len - k_len; j++) {
          if (newMap[i][j] !== 1) {
            return false;
          }
        }
    }
    return true;
}

📘 참고

http://yoonbumtae.com/?p=3247
https://velog.io/@tunakim/프로그래머스JS-자물쇠와-열쇠