🕊 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, col00 부터 bigLock.length까지 11 씩 증가시킴
    (bigLock은 재사용이 필요하기 때문에 copyBigLock으로 clone)

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

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

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

풀이 이미지

  • 세팅 후 이동 시,
  • 첫번째 검증 시, 파란 사각형 속에 1이 아닌 2, 0이 있기 때문에 break
  • 검증 도중(rotateCnt 11, row 33, col 33),
    파란 사각형 속의 모든 숫자가 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

profile
protect me from what i want

0개의 댓글