문제 : spiralTraversal

2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다.

let matrix = [
  ['A', 'B', 'C'],
  ['D', 'E', 'F'],
  ['G', 'H', 'I'],
];
let output = spiralTraversal(matrix);
console.log(output); // --> 'ABCFIHGDE'

matrix = [
  ['T', 'y', 'r', 'i'],
  ['i', 's', 't', 'o'],
  ['n', 'r', 'e', 'n'],
  ['n', 'a', 'L', ' '],
];
output = spiralTraversal(matrix);
console.log(output); // --> 'Tyrion Lannister'

문제의 접근

문제만 보고는 처음에는 이해를 못했는데 예제를 통해서 이해할 수 있었다. 이전 문제의 약간 응용버전 같은 느낌이었다.

일단 큰 그림을 그리는데 집중했다. 이 메트릭스 모양에서 윗변을 순서대로 넣어주고 오른쪽면을 순서대로 넣어준다. 그리고 바닥쪽을 역순으로 넣어주고 왼쪽면을 역순으로 넣어준다. 이 모양을 함수로 만들어 보았다.

const insertTop = (matrix, result) => {
  for(let el of matrix[0]){
    result += el;
  }
  matrix.shift();
  return result
}

const insertRight = (matrix, result) => {
  for(let i = 0; i < matrix.length; i++){
    let char = matrix[i].pop();
    result += char
  }
  return result
}

const insertBottom = (matrix, result) => {
  matrix[matrix.length-1].reverse();
  for(let el of matrix[matrix.length-1]){
    result += el;
  }
  matrix.pop();
  return result
}

const insertLeft = (matrix, result) => {
  for(let i = matrix.length-1; i >= 0; i--){
    let char = matrix[i].shift();
    result += char;
  }
  return result
}

이제 이 함수들을 계속해서 실시해주면 된다.

const spiralTraversal = function (matrix) {
  // TODO: 여기에 코드를 작성합니다.
  let result = '';

  while(true){
    insertTop(matrix,result)
    if(matrix.length === 0) break;
    insertRight(matrix,result)
    insertBottom(matrix,result)
    if(matrix.length === 0) break;
    insertLeft(matrix,result)
  }

  return result;
};

완벽했다. 사실 while문의 조건을 matrix.length > 0으로 주려했지만 생각해보니 이렇게하면 알고리즘의 처음시작에만 확인하고 실행도중 쓰레기값이 들어갈 것 같아서

무한루프를 주고 배열을 지울때마다 확인을 해주는 형식으로 바꿨다. 정말 치밀하다고 생각했지만 결과는 계속해서 빈 배열이 나왔다...

침착하게 콘솔로그로 함수 하나하나를 돌리며 확인해보니 역시나 result는 계속 빈 배열로 나왔다. 왜 그럴까를 생각해보았다. 그러다 문득 함수를 끝나고 리턴해주는 값은 어디로 갔을까? 하는 생각을 했다.

예상대로 그 값은 함수가 끝남과 동시에 사리자고 내가 선언해준 result는 계속 빈 배열이었다. 때문에 함수를 이렇게 수정해 줬다.

const spiralTraversal = function (matrix) {
  // TODO: 여기에 코드를 작성합니다.
  let result = '';

  while(true){
    result = insertTop(matrix,result)
    if(matrix.length === 0) break;
    result = insertRight(matrix,result)
    result = insertBottom(matrix,result)
    if(matrix.length === 0) break;
    result = insertLeft(matrix,result)
  }

  return result;
};

함수를 통해 실행된 값을 계속해서 result에 할당해주니 문제없이 통과되었다.

문제를 통해 생각해 볼 것

좋은 문제였다. 충분히 고민하고 문제를 해결했을 때 짜릿함을 느낄 수 있었다. 한 가지 아직 조금 스코프에 관한 실수를 조금 하는 것 같았다. 하지만 침착하게 그 문제의 원인을 파악하고 해결해가는 능력을 키울수 있었던 것 같다.

Reference

const spiralTraversal = function (matrix) {
  // 각 방향마다 row와 col의 변화를 저장
  const RIGHT = [0, 1];
  const DOWN = [1, 0];
  const LEFT = [0, -1];
  const UP = [-1, 0];
  // 각 방향을 위한 lookup table
  const MOVES = [RIGHT, DOWN, LEFT, UP];
  const M = matrix.length;
  const N = matrix[0].length;
  const isValid = (row, col) => row >= 0 && row < M && col >= 0 && col < N;

  let cnt = 0;
  let row = 0,
    col = -1;
  let direction = 0;
  let result = '';
  while (cnt < M * N) {
    const move = MOVES[direction];
    const [rd, cd] = move;

    row = row + rd;
    col = col + cd;
    while (isValid(row, col) && matrix[row][col] !== false) {
      result = result + matrix[row][col];
      // 한 요소를 두 번 접근하지 않게 하기 위해서, 접근된 요소를 false로 변경한다.
      matrix[row][col] = false;
      row = row + rd;
      col = col + cd;
      cnt++;
    }
    // row, col 이 행렬의 범위를 벗어났기 때문에,
    // 진행된 방향의 반대로 한 칸 이동한다.
    row = row - rd;
    col = col - cd;

    // 각 방향이 순환되기 때문에 모듈러 연산을 사용한다.
    direction = (direction + 1) % 4;
  }
  return result;
};