자물쇠와 열쇠

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

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

무언가 최적화된 알고리즘이 있을꺼 같아서 찾아 봤지만, 전체 검색을 제외 하고는 특별한 방법이 없었던거 같다.

key의 length와 Lock의 Length를 위, 아래, 좌, 우 합쳐진 큰 네모로 만들고 가운데에 Lock을 위치 시켜 full search 했다.

Rotation은 컬럼을 Row로 만드는 방식을 90도 순환 시켰다.

 

function solution(key, lock) {
    let fullRow = lock.length + (key.length  - 1) * 2;
    let fullBoard = new Array(fullRow).fill(0).map(()=>new Array(fullRow).fill(0));

    let lockStartPoint = key.length -1;

    for(let row = 0; row < lock.length ; row++){
        for(let col = 0; col < lock.length; col++){
            fullBoard[row+lockStartPoint][col+lockStartPoint] = lock[row][col];
        }
    }

    let boardCopy = JSON.stringify(fullBoard);

    let keyLimit = lock.length + (key.length - 1);


    for(let i =0 ; i < 4; i++){
        for(let row = 0; row < keyLimit ; row++) {
            for (let col = 0; col < keyLimit; col++) {
                let board = copyKey(row, col, JSON.parse(boardCopy), key);
                if (checkValid(board, lockStartPoint, keyLimit)) return true;
            }
        }
        key = rotate(key);
    }

    return false;

    function rotate(key){
        let rotArr = new Array();
        for(let col = 0; col < key.length; col++){
            for(let row = key.length - 1; 0 <= row; row--){
                if(rotArr[col] == null) rotArr[col] = new Array();
                rotArr[col].push(key[row][col]);
            }
        }

        return rotArr;
    }


    function copyKey(bRow, bCol, board, key) {
        for (let row = 0; row < key.length; row++) {
            for (let col = 0; col < key.length; col++) {
                board[row + bRow][col + bCol] = board[row + bRow][col + bCol] ^ key[row][col];
            }
        }
        return board;
    }

    function checkValid(board, lockStartPoint, keyLimit){
        for (let row = lockStartPoint; row < keyLimit; row++) {
            for (let col = lockStartPoint; col < keyLimit; col++) {
                if(board[row][col] == 0) return false;
            }
        }
        return true;
    }

}

console.assert(solution([[1, 0, 0], [0, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [1, 1, 0]]),"success 1");
console.assert(solution([[0, 1, 0], [1, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]),"success 2");
console.assert(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]),"success 3");
console.assert(solution([[1, 1, 0], [0, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [1, 0, 1]]),"success 4");
console.assert(solution([[1, 0, 0], [0, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [1, 0, 1]]),"success 5");
console.assert(solution([[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [1, 0, 1]]),"fail 1");
console.assert(solution([[0, 0, 0], [0, 1, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [0, 0, 1]]),"fail 2");