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

문제링크 👉 https://programmers.co.kr/learn/courses/30/lessons/60059

처음 문제를 봤을 때 접근법이 쉽게 떠오르지 않았다 ㅠㅠ
다른 분들의 풀이를 참고해서 내 것을 만드는데 조금은 걸렸던 문제이다.
하지만 접근방식만 제대로 이해하면 풀어낼 수 있다 !

문제 설명

문제설명 아래쪽에 빼꼼 문제를 풀어내는 힌트가 주어진다.

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

문제를 접근하는 방식은

1. 2차원 자물쇠 배열을 확장해서 생각하자. 그림으로 보면 아래와 같은데, lock의 길이 * lock의 길이 만큼의 checkBoard판을 생성한다.
   

2. 열쇠를 정 가운데 lock부분과 겹치는 부분에서 시작하여 끝까지 순회하면서 열쇠가 딱 들어맞는 곳을 찾아본다. (코드 상에는 계산이 귀찮아서 0, 0부터 시작했다)

3. 딱 들어맞는 곳이 있을 때까지 90도 씩 열쇠를 회전하면서 순회한다.

예시의 답은 다음과 같다. 90도 회전한 열쇠를 아래 처럼 끼워주면 딱 맞는다.

이를 코드로 짜면 아래처럼 짤 수 있다.

나의 코드

// 배열 90도 회전
const rotate90 = (arr) => {
  let temp = Array.from(Array(arr.length), () => Array(arr.length).fill(0));

  arr.forEach((row, y, arr) => {
    row.forEach((column, x) => {
      temp[y][x] = arr[arr.length - x - 1][y];
    });
  });
  return temp;
};

// 자물쇠와 열쇠가 맞는지 체크
const check = (board, lockLength) => {
    const temp = Array.from(Array(lockLength), () => Array(lockLength).fill(null))
    for (let i = lockLength; i < lockLength * 2; i++) {
        for (let j = lockLength; j < lockLength * 2; j++) {
            if (board[i][j] !== 1) return false; 
        }
    }
    return true;
}

function solution(key, lock) {
    const len = lock.length;
    
    // checkBoard 초기화 (예시 1 -> 9 * 9 배열을 생성)
    let checkBoard = Array.from(Array(len * 3), () => Array(len * 3).fill(null));
    for (let i = len; i < len * 2; i++) {
        for (let j = len; j < len * 2; j++) {
            checkBoard[i][j] = lock[i - len][j - len];
        }
    }
    for (let _ = 0; _ < 4; _++) {
        // key배열을 90도씩 4번 돌아가면서 check
        key = rotate90(key)
        
        for (let i = 0; i < checkBoard.length - key.length; i++) {
            for (let j = 0; j < checkBoard.length - key.length; j++) {
                // tempBoard를 초기화하고, board에 key를 맞춰보기(채워나가기)
                let tempBoard = [...checkBoard.map(v => [...v])];
                for (let n = 0; n < key.length; n++) {
                    for (let m = 0; m < key.length; m++) {
                        tempBoard[i + n][j + m] += key[n][m]
                    }
                }
                // key를 맞춰본 tempBoard를 순회하면서 자물쇠랑 열쇠랑 딱 맞으면 true 반환
                if (check(tempBoard, len)) return true;
            }
        }
    }
    // key랑 board랑 다 맞춰봐도 안되면 false 반환
    return false
}

제 답은 수많은 답 중 하나입니다. 효율적인 답이 있다면 공유해주세요 😁