[프로그래머스#JS] 자물쇠와 열쇠

문제

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

접근 과정

1. 문제를 보자마자 완전탐색 문제라고 생각했다.
2. 90도씩 회전하므로 원본, 90도, 180도, 270도 4가지 고려.
3. (key 배열의 길이(파랑) + lock 배열의 길이(빨강) -1)의 길이만큼 한칸씩 이동하면서 가로, 세로 탐색.

   예제 입력과 다르게 lock배열 4칸으로 구성

4. 탐색하기 위해서 (key배열의 길이 X 2) + lock(빨강) -2 길이의 새로운 배열 생성
5. 빨간색 범위의 두 배열의 값이 둘 다 1인 경우와 둘 다 0인경우 false
6. 시간 복잡도 O(N^2)
   • lock 배열의 길이 n, key 배열의 길이 m, 회전 4가지 ( n > m )
   • (n-m-1)^2 * 4

분석

1. 큰 배열 생성
   • 큰 배열 생성 후, 고정되어야 하는 lock배열 값 삽입

  const lock_len = lock.length;
  const key_len = key.length;
  const arr_len = lock_len + key_len * 2 - 2;
  const arr = Array.from(Array(arr_len), () => Array(arr_len).fill(null));

  for (let i = key_len - 1; i <= arr_len - key_len; i++) {
    for (let j = key_len - 1; j <= arr_len - key_len; j++) {
      arr[i][j] = lock[i - key_len + 1][j - key_len + 1];
    }
  }

2. 회전
   • newKey로 깊은 복사 후 return
   • 90도로 회전하기 때문에 재사용

const rotate = (key) => {
  const m = key.length;
  const newKey = Array.from(Array(m), () => Array(m).fill(null));
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < m; ++j) {
      newKey[i][j] = key[m - 1 - j][i];
    }
  }
  return newKey;
};

3. 탐색 구현
   • 큰 배열의 인덱스를 조작하여 key 배열과 비교.
   • key 배열의 길이 만큼만 큰 배열을 탐색한다.
   • x : 오른쪽 이동. y : 아래쪽 이동
   • i, j: key 배열의 길이.
   • [x+i]와 [y+j]를 이용하여 큰 배열의 탐색을 제한
   • 둘 다 1이면 2대입, 둘 다 0이면 0 대입.

    for (let x = 0; x < lock_len + key_len - 1; x++) {
      for (let y = 0; y < lock_len + key_len - 1; y++) {
        const newArr = arr.map((v) => v.slice());

        for (let i = 0; i < key_len; i++) {
          for (let j = 0; j < key_len; j++) {
            if (newArr[x + i][y + j] === 1 && key[i][j] === 1) {
              newArr[x + i][y + j] = 2;
            } else if (newArr[x + i][y + j] === 1 && key[i][j] === 0) {
              newArr[x + i][y + j] = 1;
            } else if (newArr[x + i][y + j] === 0 && key[i][j] === 1) {
              newArr[x + i][y + j] = 1;
            } else {
              newArr[x + i][y + j] = 0;
            }
          }
        }         

4. 검증
   • 빨간 범위안에 배열 탐색 -> 0이나 2가 있으면 false return

function isAnswer(newArr, key_len, arr_len) {
  for (let i = key_len - 1; i <= arr_len - key_len; i++) {
    for (let j = key_len - 1; j <= arr_len - key_len; j++) {
      if (newArr[i][j] !== 1) {
        return false;
      }
    }
  }
  return true;
}

코드

const rotate = (key) => {
  const m = key.length;
  const newKey = Array.from(Array(m), () => Array(m).fill(null));
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < m; ++j) {
      newKey[i][j] = key[m - 1 - j][i];
    }
  }
  return newKey;
};

function isAnswer(newArr, key_len, arr_len) {
  for (let i = key_len - 1; i <= arr_len - key_len; i++) {
    for (let j = key_len - 1; j <= arr_len - key_len; j++) {
      if (newArr[i][j] !== 1) {
        return false;
      }
    }
  }
  return true;
}

function solution(key, lock) {
  const lock_len = lock.length;
  const key_len = key.length;
  const arr_len = lock_len + key_len * 2 - 2;
  const arr = Array.from(Array(arr_len), () => Array(arr_len).fill(null));

  for (let i = key_len - 1; i <= arr_len - key_len; i++) {
    for (let j = key_len - 1; j <= arr_len - key_len; j++) {
      arr[i][j] = lock[i - key_len + 1][j - key_len + 1];
    }
  }

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

    for (let x = 0; x < lock_len + key_len - 1; x++) {
      for (let y = 0; y < lock_len + key_len - 1; y++) {
        const newArr = arr.map((v) => v.slice());

        for (let i = 0; i < key_len; i++) {
          for (let j = 0; j < key_len; j++) {
            if (newArr[x + i][y + j] === 1 && key[i][j] === 1) {
              newArr[x + i][y + j] = 2;
            } else if (newArr[x + i][y + j] === 1 && key[i][j] === 0) {
              newArr[x + i][y + j] = 1;
            } else if (newArr[x + i][y + j] === 0 && key[i][j] === 1) {
              newArr[x + i][y + j] = 1;
            } else {
              newArr[x + i][y + j] = 0;
            }
          }
        }

        if (isAnswer(newArr, key_len, arr_len)) {
          return true;
        }
      }
    }
  }

  return false;
}

느낀점

• 생각하기 쉬운 완전탐색이지만 구현하기가 너무 어려웠다.
• 큰 배열을 만들지 않고 겹치는 부분만 조건을 걸어 비교하려 했더니 너무 복잡해져서 결국 구글링 했다.
• 카카오 해설을 보면 lock배열 길이의 * 3 으로 큰 배열을 설정해 편하게 구현했지만 처음에 접근했던 대로 구현해보기 위해 n + (m X 2) - 2로 재구현해봤다.
• kyun2da님 블로그 참고 했습니다.