자물쇠와 열쇠

자물쇠와 열쇠

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길이 세 배의 행렬을 만들지도 않았고,

• 행렬을 매번 복제하지 않고 기존 행렬을 수정하는 방식으로 풀어서 그런 것 같다.

• 천잰가...

• 세 배 길이의 행렬을 만들지 않고 푸는 건 도저히 흉내를 못내겠고, 매번 복제하는 로직은 수정할 수 있을 것 같아서 아래와 같이 수정해봤다.

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, operator) {
  const length = key.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      board[rowStart + i][colStart + j] +=
        operator == "do" ? key[i][j] : key[i][j] * -1;
    }
  }
}

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;
  const board = makeBoard(lock);
  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++) {
        matchKey(j, k, board, key, "do");
        if (isMatched(board)) {
          return true;
        }
        matchKey(j, k, board, key, "undo");
      }
    }
  }
  return false;
}

• 회전시키는 함수까지 복제가 아닌 수정으로 바꾸면 좋았겠지만, 지금은 이해가 안되니 ㅠㅠ