프로그래머스 LEVEL 3(자물쇠와 열쇠)

사용 언어 : javascript
해결 날짜 : 2023-04-26
해결 방법 :
- 2차원 슬라이딩 윈도우를 활용해 문제 해결
  - key를 90도씩 3번 회전 (총 4개, 0도 90도 180도 270도)
  - 슬라이딩 윈도우를 움직여가며 빈 홈에 맞는지 확인
    - 이 때 슬라이딩 윈도우는 [0, 0]부터가 아닌 [-key.length, -key.length]부터 시작
    - 즉, key의 맨 우측 하단 한칸이 lock의 맨 좌측 상단 한칸에 걸리는 위치부터 시작
    - 한 칸씩 움직여가며 lock의 빈 부분에 채운 뒤 lock이 전부 채워졌다면 true 반환
회고 :
- 처음에 슬라이딩 윈도우를 [0, 0]부터 시작한다고 생각해 해결하는데 시간이 오래 걸렸다.
- 슬라이딩 윈도우를 [-key.length, -key.length]부터 시작하도록 변경하니 성공했다.

코드

const rotate = (key) => {
  const temp = key.map((v) => [...v]);

  for (let i = 0; i < key.length; i++) {
    for (let j = 0; j < key.length; j++) {
      key[i][j] = temp[key.length - j - 1][i];
    }
  }
};

const isMatch = (key, lock, row, col) => {
  const temp = lock.map((v) => [...v]);

  for (let i = 0; i < key.length; i++) {
    for (let j = 0; j < key.length; j++) {
      if (row + i < 0 || col + j < 0 || row + i >= lock.length || col + j >= lock.length) {
        continue;
      }

      if (key[i][j]) {
        if (temp[row + i][col + j]) {
          return false;
        } else {
          temp[row + i][col + j] = 1;
        }
      }
    }
  }

  return !temp.flat().some((v) => v === 0);
};

function solution(key, lock) {
  for (let i = 0; i < 4; i++) {
    for (let j = -key.length; j < lock.length; j++) {
      for (let k = -key.length; k < lock.length; k++) {
        if (isMatch(key, lock, j, k)) {
          return true;
        }
      }
    }

    if (i !== 3) rotate(key);
  }

  return false;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges