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

문제

2020 카카오 블라인드 채용 - 자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059

 

 

풀이

설명

열쇠로 자물쇠를 열 수 있는지를 구하는 문제입니다.

 

주의할 점은 다음과 같습니다.

• 열쇠는 회전과 이동이 가능하다.
• 열쇠의 크기는 자물쇠의 크기와 같거나 작다.
• 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않는다.
• 자물쇠 영역 내에서는 열쇠의 돌기 부분은 자물쇠의 홈 부분과 만나야 한다.
• 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 한다.

 

열쇠는 총 3번 회전할 수 있으므로 4가지 모양으로 시도 가능합니다.

열쇠의 위치는 x, y 각각 -M + 1부터 N - 1까지 가능합니다.

 

예시 코드

function solution(key, lock) {
  const M = key.length;
  const N = lock.length;
  let lockHoles = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (lock[i][j] === 0) lockHoles++;
    }
  }

  for (let rot = 0; rot < 4; rot++) {
    key = rotate(key);

    for (let i = -M + 1; i < N; i++) {
      for (let j = -M + 1; j < N; j++) {
        if (check(key, i, j)) return true;
      }
    }
  }

  return false;

  function rotate(key) {
    const newKey = [];

    for (let i = 0; i < M; i++) {
      newKey[i] = [];

      for (let j = 0; j < M; j++) {
        newKey[i][j] = key[M - j - 1][i];
      }
    }

    return newKey;
  }

  function check(key, x, y) {
    let filledHoles = 0;

    for (let i = 0; i < M; i++) {
      for (let j = 0; j < M; j++) {
        const lockX = x + i;
        const lockY = y + j;
        if (lockX < 0 || lockX >= N || lockY < 0 || lockY >= N) continue;
        if (key[i][j] === lock[lockX][lockY]) return false;
        if (key[i][j] === 1 && lock[lockX][lockY] === 0) filledHoles++;
      }
    }

    return lockHoles === filledHoles;
  }
}