[프로그래머스] 60059 자물쇠와 열쇠 - 자바스크립트

안녕하세요 동쪽별입니다. 

친구들과 알고리즘 스터디를 진행하면서 매주 다섯 문제씩 풀고 있는데요.

오늘부터 매주 해결한 문제 중 가장 어려웠던 문제 하나를 꼽아 리뷰하려 합니다 😁

(개인적으로 어려웠던 문제가 더 있다면 두개 이상 올릴거에요)

어려운 문제인 만큼 여러 사람들에게 도움을 줄 수 있겠다 싶었거든요. 더군다나 자바스크립트로 풀었기에..!

 

문제

코딩테스트 연습 - 자물쇠와 열쇠

 

로직

1. 주어진 lock의 홈 패턴을 구합니다.

• 여기서 패턴이란 하나의 홈에서 나머지 홈까지의 거리만을 구하여 저장해놓는 것을 의미합니다.
• lock을 순회하며 가장 먼저 발견한 홈을 저장해두고, 이후 발견하는 홈에 대한 거리(row와 col의 차)를 계산하고 저장합니다.
• 이처럼 미리 패턴을 구해놓으면 key의 회전만 신경쓰면 됩니다. (전부 이동해보는 것은 비효율적이니까요)

 

2. key를 순회하며 돌기일 경우 lock의 홈 패턴에 맞는지 확인합니다.

• 해당 돌기의 위치를 기준으로 생성한 lock의 홈 패턴, 즉 거리들을 더한 위치들 또한 모두 돌기인지 확인합니다.
• 패턴에 맞지 않을 경우(모두 돌기가 아닌 경우), key를 회전하고 다시 2를 수행합니다.
• 맞을 경우(모두 돌기인 경우), key와 lock의 돌기가 서로 맞닿아 있는지 확인해야 합니다.
  • 이때, key의 돌기 패턴을 구합니다. (lock의 홈 패턴을 구했던 것 처럼) 
  • 구한 패턴을 따라 lock을 탐색하며 돌기를 발견시 break한 후 다시 2를 수행합니다.
• 돌기가 서로 맞닿아 있는 경우가 없으면 true를 리턴합니다.

 

3. key를 세번 회전하고도 lock을 풀 수 없으면(lock의 패턴에 맞지 않으면) false를 리턴합니다.

 

코드

⏱ 시간 복잡도 :  O(n^3)

// 열쇠 회전
function rotateKey(key) {
  const M = key.length;
  const rotated = [];

  for (let y = 0; y < M; y++) {
    const col = [];
    for (let x = M - 1; x >= 0; x--) {
      col.push(key[x][y]);
    }
    rotated.push(col);
  }
  return rotated;
}

// 홈 또는 돌기 패턴 얻기
function getPattern(target, state, start = null) {
  const pattern = {
    start: start,
    direction: []
  };

  target.forEach((row, x) => {
    row.forEach((value, y) => {
      if (value != state) {
        return;
      }
      if (!pattern.start) {
        pattern.start = [x, y];
        return;
      }
      const dx = x - pattern.start[0];
      const dy = y - pattern.start[1];
      if (dx || dy) {
        pattern.direction.push([dx, dy]);
      }
    });
  });

  return pattern;
}

// 자물쇠 풀기
function unlock(key, lock, pattern) {
  const M = key.length;
  const N = lock.length;

  const isIndexOut = (x, y, n) => {
    if (x < 0 || x >= n || y < 0 || y >= n) {
      return true;
    }
    return false;
  }

  // 자물쇠 돌기와 열쇠 돌기가 만나는지 확인
  const checkJutMeet = ({ keyStart, lockStart }) => {
    const [x, y] = lockStart;
    const keyPattern = getPattern(key, true, keyStart);

    for (const [dx, dy] of keyPattern.direction) {
      const [nextX, nextY] = [x + dx, y + dy];
      if (isIndexOut(nextX, nextY, N)) {
        continue;
      }
      if (lock[nextX][nextY]) {
        return false;
      }
    }
    return true;
  }

  // 자물쇠 홈을 모두 채울 수 있는지 확인
  const checkPattern = (x, y) => {
    for (const [dx, dy] of pattern.direction) {
      const [nextX, nextY] = [x + dx, y + dy];
      if (isIndexOut(nextX, nextY, M) || !key[nextX][nextY]) {
        return false;
      }
    }

    if (checkJutMeet({
      keyStart: [x, y],
      lockStart: pattern.start 
    })) {
      return true;
    }
    return false;
  }

  // 해당 열쇠로 자물쇠를 풀 수 있는지 확인
  for (let x = 0; x < M; x++) {
    for (let y = 0; y < M; y++) {
      if (!key[x][y]) {
        continue;
      }

      if (checkPattern(x, y)) {
        return true;
      }
    }
  }
  return false;
}

function solution(key, lock) {
  // 자물쇠 홈 패턴 얻음
  const unlockPattern = getPattern(lock, false);
  let answer = false;

  // 자물쇠 홈이 없음
  if (!unlockPattern.start) {
    return true;
  }

  for (let i = 0; i < 4; i++) {
    if (i > 0) {
      key = rotateKey(key);
    }
    if (unlock(key, lock, unlockPattern)) {
      answer = true;
      break;
    }
  }

  return answer;
}

 

리뷰

문제를 읽자마자 키를 전부 이동시켜보는 것은 매우 비효율적이라 생각했고, 따라서 회전 만을 통해 문제를 해결하려 했다.

그림을 자꾸 보며 고민하다 자물쇠 홈 패턴을 구하여 열쇠의 회전만으로 해당 자물쇠를 풀 수 있는지 여부를 확인하는 아이디어를 떠올렸다.

대부분의 스터디원들은 주어진 lock과 key의 크기가 최대 20인 것을 보고, key를 lock의 왼쪽 대각선부터 오른쪽 대각선으로 이동시키며 전부 확인하는 방법으로 해결했다.

해당 방법은 나의 방법에 비해 구현이 쉽고 코드가 비교적 적다는 장점이 있지만, 시간 복잡도는 O(n^4)이기에 성능 측면에서는 나의 방법이 효율적인 것 같다.