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

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

 

문제 요약 :

1. 자물쇠의 빈 공간에 열쇠의 돌기가 맞아야 한다.
2. 자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안 된다.
3. 키는 특정 부분만 사용하여 자물쇠를 열 수 있다.

 

문제 풀이 시간 :  1시간 30분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. 자물쇠에 대해 가능한 모든 열쇠 모양을 시뮬레이션

문제에서 주어진 예시

 

다음과 같은 키와 자물쇠가 주어진다고 보자.

 

자물쇠에 대해 모든 key 모양을 다 대입시키려면, 적어도 키의 한 칸은 자물쇠와 맞물려야 한다.

 

따라서, 자물쇠의 가장 왼쪽 상단(0,0)을 key의 가장 오른쪽 아래인 (2,2)를 맞물려본다.

키를 자물쇠의 가장 왼쪽 위에 맞물리게 하였다.

 

키를 시계방향으로 90도 회전하면 이렇게 된다.

이 과정을 반복하면 결국 모든 경우의 수를 다 확인할 수 있다.

 

 

이 풀이방법을 위한 준비물은 다음과 같다.

 

1. key를 시계방향으로 회전시킨 4개의 배열(0,90,180,270)

2. 위와 같은 그림과 같이, 모든 키를 대입할 수 있는 중앙배치된 자물쇠 배열(arr)

 

1번은 말 그대로 key 배열을 90도씩 돌려가며, 저장해 두면 된다.

2번은 (keyRow-1 + lockRow + keyRow-1) * (keyCol-1 + lockCol + keyCol-1)의 배열을 만들고 중앙에 lock을 복사하면 된다.

 

그렇다면 시간복잡도는 어떻게 될까?

 

위의 표를 기준으로 보면 (0,0) ~ (4,4)까지 각각의 인덱스에 대해 4번의 검사(키를 회전한 4번 비교)를 진행한다.

 

식으로 표현하면 4 * (N+M-1)^2만큼의 탐색이 고정적으로 진행된다고 보면 된다.

 

또한, 검사를 진행할 때 M*M개를 arr에 대입해 보고 자물쇠 크기인 N*N을 검사하고 M*M개를 다시 원상복구 시킨다고 보면

4*(N+M-1)^2 * (M*M+N*N+M*M) 정도의 시간이 걸린다고 보면 된다.(물론 더 효율적으로 검사할 수 있는 방법이 있다.)

 

N과 M이 최대 20까지 올 수 있기에 총 연산 횟수는 약 7백만 개임으로 시간초과의 걱정은 없다.

 

 

 

이제 구현만이 남았는데, 살짝 골치 아팠던 회전 로직을 설명해 보겠다.

 

회전 로직

const getRotateImages = (arr) => {
    const rotateImages = [arr];
    
    for(let i=0; i<3; i++){
        const rotateImage = getRotateImage(rotateImages[i]); // 이전 배열을 넣어 90도씩 회전시킨다.
        rotateImages.push(rotateImage);
    }
    return rotateImages;
}

 

해당 함수는 배열을 입력받아 0도, 90도, 180도, 270도 회전시킨 4가지 배열을 반환해 주는 함수이다.

이전 결괏값(배열)을 인자로 getRotateImage 함수에 넣어 계속 90도씩 돌려준다.

 

const getRotateImage = (arr) => {
    const len = arr.length;
    const rotateImage = Array.from({length:len}, ()=>Array(len).fill(0));
    
    for(let i =0; i<len; i++){
        for(let j=0; j<len; j++){
            rotateImage[j][len-1-i] = arr[i][j]; // 90도 회전시킨다.
        }
    }
    return rotateImage;
}

 

회전 핵심 로직이다.

규칙을 생각한다고 시간을 꽤나 잡아먹었는데 코드는 아주 간단하다.

 

1. 현재 인덱스의 값은 회전하게 되면 col 값이 row 값이 된다.

2. row 값은 (len-1)- row를 한 값이 col이 된다.

 

해당 규칙을 코드로 구현하여 해결하였다.

 

검사 로직

검사 로직은 솔직히 좀 비효율적으로 구현하였다.

이전에 빼앗긴 시간을 급하게 해결하기 위해 쉽지만 다소 비효율적인 방법으로 접근하였다.

 

key 배열이 주어질 때, 가장 쉽게 비교할 수 있는 방법은 다음과 같다.

 

1. arr 배열 각각의 인덱스에 key 배열 각각의 인덱스 값을 더해준다.

2. lock 부분을 탐색하며 1이 아닌 값이 있을 경우 false, 없을 경우 true임을 알 수 있다.

3. 원본 arr 배열의 값이 변했기 때문에 다시 key 배열 각각의 인덱스 값을 빼준다.

 

const check = (arr,x,y,rotateImage) => {
    const keyLen = rotateImage.length-1;
    for(let i=x; i<=x+keyLen; i++){
        for(let j=y; j<=y+keyLen; j++){
            arr[i][j] += rotateImage[i-x][j-y]; // arr에 key값을 더해준다.
        }
    }
    
    const len = arr.length;
    let isTrue = true;
    for(let i=keyLen; i<len-keyLen; i++ ){
        for(let j=keyLen; j<len-keyLen; j++){
            if(arr[i][j]!==1) { // 2거나 0이면 열 수 없으므로 false
                isTrue = false;
                break;
            }
        }
    }
    
    for(let i=x; i<=x+keyLen; i++){ 
        for(let j=y; j<=y+keyLen; j++){
            arr[i][j] -= rotateImage[i-x][j-y]; // key값을 다시 빼서 원상복구 시킨다.
        }
    }
    return isTrue;
}

 

전체 코드(성공) :

function solution(key, lock) {
    const keyLen = key.length-1;
    const lockLen = lock.length;
    const len = keyLen * 2 + lockLen;
    
    const arr = Array.from({length:len}, ()=>Array(len).fill(0)); // 자물쇠 중앙배치 배열
    
    for(let i=keyLen; i<keyLen+lockLen; i++){
        for(let j=keyLen; j<keyLen+lockLen; j++){
            arr[i][j] = lock[i-keyLen][j-keyLen]; // 자물쇠 중앙 배치
        }
    }
    
    const rotateImages = getRotateImages(key); // key를 회전시킨 4가지 배열 반환
    
    for(let i=0; i<len-keyLen; i++){
        for(let j=0; j<len-keyLen; j++){
            for(const rotateImage of rotateImages){
                if(check(arr,i,j,rotateImage)) return true; // 해당 위치에 4번의 회전 결과를 대입
            }
            
        }
    }
    return false;
}

const check = (arr,x,y,rotateImage) => {
    const keyLen = rotateImage.length-1;
    for(let i=x; i<=x+keyLen; i++){
        for(let j=y; j<=y+keyLen; j++){
            arr[i][j] += rotateImage[i-x][j-y]; // arr에 key값을 더해준다.
        }
    }
    
    const len = arr.length;
    let isTrue = true;
    for(let i=keyLen; i<len-keyLen; i++ ){
        for(let j=keyLen; j<len-keyLen; j++){
            if(arr[i][j]!==1) { // 2거나 0이면 열 수 없으므로 false
                isTrue = false;
                break;
            }
        }
    }
    
    for(let i=x; i<=x+keyLen; i++){ 
        for(let j=y; j<=y+keyLen; j++){
            arr[i][j] -= rotateImage[i-x][j-y]; // key값을 다시 빼서 원상복구 시킨다.
        }
    }
    return isTrue;
}

const getRotateImages = (arr) => {
    const rotateImages = [arr];
    
    for(let i=0; i<3; i++){
        const rotateImage = getRotateImage(rotateImages[i]); // 이전 배열을 넣어 90도씩 회전시킨다.
        rotateImages.push(rotateImage);
    }
    return rotateImages;
}

const getRotateImage = (arr) => {
    const len = arr.length;
    const rotateImage = Array.from({length:len}, ()=>Array(len).fill(0));
    
    for(let i =0; i<len; i++){
        for(let j=0; j<len; j++){
            rotateImage[j][len-1-i] = arr[i][j]; // 90도 회전시킨다.
        }
    }
    return rotateImage;
}