[CodeKata] 프로그래머스 : 5.1(토), 자물쇠와 열쇠

🥋 Oooth More!! (Level 3)

* 풀이 강의 링크 : programmers.co.kr/learn/courses/10336?utm_source=programmers&utm_medium=test_course10336&utm_campaign=course_10336

 

key를 90도씩 돌려, key의 돌기들로 Lock의 홈을 채울 수 있으면 된다. 단, key의 돌기가 Lock의 돌기와 만나는 경우가 있으면 안된다.

 

 🧮 풀이

function rotateArr(originalArr) {
  const N = originalArr.length;
  const rotatedArr = Array.from(Array(N), () => new Array(N).fill(null))
  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
        rotatedArr[col][N - 1 - row] = originalArr[row][col]
    }
  }
  return rotatedArr;
}

function solution(key, lock) {
  const offset = key.length - 1;
  const keyBumps = [];
  
  let rotateCount = 0;
  while (rotateCount < 4) {
    let nowBump = [];
    for (let x = 0 ; x < key.length ; x++) {
      for (let y = 0 ; y < key.length ; y++) {
        if (key[x][y] === 1) nowBump.push([x,y]);
      }
    }
    keyBumps.push(nowBump);
    key = rotateArr(key);
    rotateCount++;
  }

  for (let i = -offset ; i < lock.length + offset ; i++) {
    for (let j = -offset ; j < lock.length + offset ; j++) {
      for (let bumps of keyBumps) {
        let nowLock = JSON.parse(JSON.stringify(lock));
        bumps.forEach(bump => {
          if (i+bump[0] >= 0 && i+bump[0] < lock.length
           && j+bump[1] >= 0 && j+bump[1] < lock.length) {
            nowLock[i+bump[0]][j+bump[1]] += 1;
          }
        })

        if (nowLock.flat().every(v => v === 1)) {
          return true;
        }
      }
    }
  }

  return false;
}

- rotateArr() 2차원 배열 회전 함수

1. 이 함수는, originalArr 2차원 배열을 매개변수로 받아, rotatedArr 회전한 2차원 배열을 반환한다. 크기는 변함없이 N * N.
2. N과 Array.from() 메서드로 N * N의 빈 2차원 배열을 만들어준다.
3. 이 배열을 2중순회를 통해 각각 채워준다. 이 떄, 내부의 로직에 따라 회전하는 방향을 정할 수 있다. (위 예시는 시계방향 90도)

- key를 회전한 4가지 경우의 돌기 좌표들로 변형

1. 우선, 입력된 key를 통해 회전한 4가지 경우의 key 형태를 구해야겠다고 생각했다. rotateCount가 회전시키는 횟수이다. (총 3회)
2. 또한, key는 돌기만 필요하므로 돌기들의 좌표만 필요하다. 이를, 2중순회를 통해 nowBump 배열에 튜플들로 누적한다.
3. 마지막으로, 이 nowBump를 keyBumps 배열에 누적한다. 이어서, key를 rotateArr() 함수로 회전, rotateCount에 1을 더한다. 

- lock에 key를 맞춰보기

1. lock을 순회하며 key를 맞춰본다. 이 때, [0,0] 부터가 아닌, key의 오른쪽 아래 모서리가 lock의 왼쪽 윗 모서리와 맞닿는 경우부터 시작해야한다. 종료 역시 key의 왼쪽 윗 모서리가 lock의 오른쪽 아래 모서리와 맞닿는 경우다. 그렇기에 순회기준에 offset 값을 준다.
2. 각 위치에서 keyBumps(key가 회전하는 4가지 경우의 돌기)들을 고려한다. 이는, lock의 사본(깊은 복사)인 nowLock에 적용.
3. 현재 key인 bumps를 순회하며 nowLock의 [i + bump[0], j + bump[1]] 에 1을 더해준다. lock의 범위를 벗어나면 오류가 발생하므로 if 조건문을 먼저 실행한 것이다.
4. 마지막으로, nowLock을 flat()을 통해 1차원 배열로 만든 뒤, 여기에 1 이외의 값이 없다면 true를 반환한다.
5. 1 이외의 값이 있는 경우는 2가지다. 0은 lock의 홈을 다 못채운 경우, 2는 lock 돌기와 key 돌기가 겹쳤던 경우이다.

 

🖇 리뷰

function rotate90(matrix) {
  const length = matrix.length;
  const rotated = new Array(length)
    .fill(null)
    .map(() => new Array(length).fill(null));
  for (let col = 0; col < length; col++) {
    for (let row = length - 1; row >= 0; row--) {
      rotated[col][length - 1 - row] = matrix[row][col];
    }
  }
  return rotated;
}

function makeBoard(origin) {
  const length = origin.length;
  const board = new Array(length * 3)
    .fill(null)
    .map(() => new Array(length * 3).fill(0));
  for (let m = 0; m < length; m++) {
    for (let n = 0; n < length; n++) {
      board[m + length][n + length] = origin[m][n];
    }
  }
  return board;
}

function matchKey(rowStart, colStart, board, key) {
  const length = key.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      board[rowStart + i][colStart + j] += key[i][j];
    }
  }
}

function isMatched(board) {
  const length = board.length;
  for (let i = length / 3; i < (length / 3) * 2; i++) {
    for (let j = length / 3; j < (length / 3) * 2; j++) {
      if (board[i][j] != 1) {
        return false;
      }
    }
  }
  return true;
}

function solution(key, lock) {
  const length = lock.length;
  for (let i = 0; i < 4; i++) {
    key = rotate90(key);
    for (let j = 0; j <= length * 2; j++) {
      for (let k = 0; k <= length * 2; k++) {
        const board = makeBoard(lock);
        matchKey(j, k, board, key);
        if (isMatched(board)) {
          return true;
        }
      }
    }
  }
  return false;
}

우선, 카카오의 해설이다. 코드는 길지만 컨셉을 얘기하면, lock을 3 * 3으로 복제한 board 2차원 배열을 순회하는 방법이다.

 

rotate90() 함수는 풀이와 똑같다. 시계방향으로 90도 회전시키는 함수이며, solution() 에서도 4번동안 key를 회전시킨다.

makeBoard() 함수가 3 * 3 lock을 만드는 함수다. key가 lock을 벗어나는 경우를 위함인 것 같다.

matchKey() 함수는 시작점(x,y), board, key를 매개변수로 받으며, 시작점부터 board의 값들에 key 값을 더해준다.

isMatched() 함수가 위에서 수정된 board가 1 이외의 값을 갖는지 여부를 탐색한다.

solution에서 lock 길이의 2배까지만 탐색하는 이유는, 그 이후의 값은 matchKey에서 key.length 만큼 추가적으로 작업되기 때문이다.

 

효율성 면에서 내 풀이 대비 엄청난 차이를 보이진 않았다. 둘 다 결론적으론 key가 lock을 크게 도는 원리이기 때문일 것이다.

다만, 나는 lock의 3 * 3이 아닌 바깥 라인만 타기 때문에 어떤 면에서는 내 풀이가 좀 더 효율적으로 나온 것이 아닌가 추정된다.

 

카카오 풀이를 보며 기능별 함수분할(함수형 프로그래밍)을 연습해야겠다 생각하였고, 

그러한 측면에서, matchKey와 isMatched는 사용인자와 역할이 비슷한 점에서 하나로 묶어도 되지 않을까 나름대로 추정해보았다.