🕊 Link

Lv3. 자물쇠와 열쇠 Javascript
https://programmers.co.kr/learn/courses/30/lessons/60059

🧑🏻‍💻 Code(javascript)

function solution(key, lock) {
  const keyLength = key.length;
  const lockLength = lock.length;
  // 세팅1
  const bigLock = Array.from(Array(lockLength + keyLength * 2 - 2), () =>
    new Array(lockLength + keyLength * 2 - 2).fill(0)
  );
  // 세팅2
  for (let i = 0; i < lockLength; i++) {
    for (let j = 0; j < lockLength; j++) {
      bigLock[i + keyLength - 1][j + keyLength - 1] = lock[i][j];
    }
  }
  let rotateCnt = 0;

  while (true) {
    // 이동1
    for (let row = 0; row <= bigLock.length - keyLength; row++) {
      for (let col = 0; col <= bigLock.length - keyLength; col++) {
        const copyBigLock = bigLock.map((v) => v.slice());
        // 이동2
        for (let i = 0; i < keyLength; i++) {
          for (let j = 0; j < keyLength; j++) {
            if (key[i][j] === 1) {
              copyBigLock[i + row][j + col]++;
            }
          }
        }
        // 검증
        let flag = true;
        outer: for (let i = keyLength - 1; i < keyLength + lockLength - 1; i++) {
          for (let j = keyLength - 1; j < keyLength + lockLength - 1; j++) {
            if (copyBigLock[i][j] !== 1) {
              flag = false;
              break outer;
            }
          }
        }
        if (flag === true) return true;
      }
    }
    // 회전
    if (rotateCnt < 3) {
      const rotatedKey = Array.from(Array(keyLength), () =>
        new Array(keyLength).fill(null)
      );
      for (let i = 0; i < keyLength; i++) {
        for (let j = 0; j < keyLength; j++) {
          rotatedKey[i][j] = key[keyLength - 1 - j][i];
        }
      }
      key = rotatedKey;
      rotateCnt++;
    } else {
      return false;
    }
  }
}

💡 Solution

• 완전 탐색
• 문제 입출력 예에 대한 설명 中
  "key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다."
  다시 말 해,
  "key를 시계 방향으로 90도 회전하고 회전, 오른쪽으로 한 칸 이동(right), 아래로 한 칸이동(down) 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.검증"
• 1.회전 2.이동 3.검증 의 세가지 과정이 필요함을 알 수 있었고,
  풀이를 하면서 순서를 변경하여 1.이동 2.검증 3.회전 순으로 진행함.

풀이 과정

1. 세팅1 : lockLength + keyLength * 2 - 2 크기의 bigLock(큰 판)을 생성

2. 세팅2 : bigLock 가운데에 lock을 배치

3. 이동1 : row, col을 $0$ 부터 bigLock.length까지 $1$ 씩 증가시킴
   (bigLock은 재사용이 필요하기 때문에 copyBigLock으로 clone)

4. 이동2 : 이동을 하면서 key의 값이 1인 경우 copyBigLock의 해당 칸을 +1

5. 검증 : i와 j를 $0$ 부터 keyLength까지 $1$씩 증가시키면서,
   i + row, j + col를 확인하는데,
   그 값이 $1$ 이 아닐 경우, 검증 반복문을 break
   (0 또는 2 일 경우 조건에 부합하지 않기 때문)
   검증 단계에서 flag가 변함없이 true일 경우,
   열쇠로 자물쇠를 열 수 있는 경우이기 때문에 return true

6. 회전 :
   return 되지 않고 아래로 내려온 경우 중, rotateCnt이 $3$ 미만인 경우, 회전
   return 되지 않고 아래로 내려온 경우 중, rotateCnt이 $3$ 이상인 경우, return false
   (모든 검증 과정을 거쳤으나 통과된 케이스가 없었기 때문)

풀이 이미지

• 세팅 후 이동 시,
  
• 첫번째 검증 시, 파란 사각형 속에 1이 아닌 2, 0이 있기 때문에 break
  
• 검증 도중(rotateCnt $1$, row $3$, col $3$),
  파란 사각형 속의 모든 숫자가 1이므로 return true
  

👨🏻‍💻💭 Self Feedback

어떤 length를 써야하는지 혼동이 많았고, 그만큼 실수도 많았던 문제.
다양한 테스트코드를 적용해보고 에러를 잡았다.
디바이드 앤 컨커 : 돌리는 행위 / 이동하는 행위 / 맞춰보는 행위 ...

이중 배열 초기화

초반에 new Array를 만들 때, 참조값을 하나 만들어서 여러 곳에서 참조하면서 로직에 혼선이 있었다.

잘못된 방법

const arr1 = new Array(len).fill(new Array(len).fill(null));
안쪽 배열을 하나 만들어서 레퍼런스만 len만큼 복사하여 바깥 배열의 각 index에 참조시킴
(안쪽 배열을 하나만 만들어서 여러 곳에서 참조함)

옳은 방법

const arr2 = Array.from(Array(len), () => new Array(len).fill(null));
바깥쪽 배열에서 각 index를 돌면서 새로 len길이의 배열을 만들어 참조시킴

• 2021.04.25 - 최초 작성

댓글 환영 질문 환영
by.protect-me