[JS 알고리즘] Toy 23 - spiralTraversal

해당 문제는 코드스테이츠의 Toy problem을 출처로 합니다.
2022.05.13

문제

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

입력

인자 1 : matrix

• 세로 길이(matrix.length)가 M, 가로 길이(matrix[i].length)가 N인 2차원 배열
• matrix[i]는 string 타입을 요소로 갖는 배열
• matrix[i][j].length는 1

출력

• string 타입을 리턴해야 합니다.

주의사항

• 순회는 좌측 상단 (0,0)에서 시작합니다.
• 배열의 모든 요소를 순서대로 이어붙인 문자열을 리턴해야 합니다.

입출력 예시

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'

 

 

접근 방법

 문제를 보고 메모이제이션 기법으로 순회한 요소의 위치에 true / false 표시하는 기법도 있겠다 싶었다.

다만 메모하지 않아도 풀 수 있을 것 같길래 나는 일단 단순하게 접근해보기로 했다.

rightward, downward, leftward, upward 각각을 방향대로 나눠 순회 및 접근하고 이를 결과 배열에 담아 스트링 조인해주는 방식으로 구현했다.

 

 

작성 코드 (Javascript)

const spiralTraversal = function (matrix) {
  let result = [];
  let totalSize = matrix.length * matrix[0].length;
  
  let rowFront = 0;
  let rowRear = matrix.length - 1;
  let colFront = 0;
  let colRear = matrix[0].length - 1;

  // rightward, downward, leftward, upward 언제 순회가 끝날지 모르므로 값을 넣기 전에 항상 검증
  const validAndPush = (el) => {
    if (result.length < totalSize)
      result.push(el)
    else 
      return result.join('')
  }

  while (result.length < totalSize) {
    // rightward
    for (let j = colFront; j <= colRear; j++) {
      validAndPush(matrix[rowFront][j])
    }
    // downward
    for (let i = rowFront + 1; i <= rowRear; i++) {
      validAndPush(matrix[i][colRear])
    }
    // leftward
    for (let j = colRear - 1; j >= colFront; j--) {
      validAndPush(matrix[rowRear][j])
    }
    // upward
    for (let i = rowRear - 1; i > rowFront; i--) {
      validAndPush(matrix[i][colFront])
    }
    // 한 회전이 끝났으므로 다음 순회를 위해 front++, rear--값 조정
    rowFront++;
    rowRear--;
    colFront++;
    colRear--; 
  }

  return result.join('');
};

 

 클린코드를 위해서는 "단일책임원칙", 하나의 함수에는 최대한 하나의 기능이 들어가도록 구현해야하지만, 부득이하게 valideAndPush 라는 검증과 값 추가를 동시에 수행하는 함수로 빼서 구현했다...

 아직은 내공이 부족해서 그런 것 같다. 코드를 직접 작성하는 것 만큼 좋은 코드를 눈으로 많이 익히는 것이 정말 중요하다는 걸 매순간 느낀다.

 

Reference Code (Javascript)

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;
};

---

배운점 및 느낀점

 레퍼런스 코드가 알고리즘 체계와 가독성이 더 좋은 것 같다!

 

 레퍼런스 코드는 각 방향마다 좌표의 변화, 그리고 방향명을 배열에 담고 배열 원소에 접근하는 방식으로 구현했다.

코드를 딱 봤을때 어떤 문제를 해결하려고 하는 것인지, 어떤 식으로 접근해서 해결하려고 하는 지가 한눈에 보인다.

로직에 집중할 수 있도록 깔끔하게 코드를 짜는 법을 배우자!

 

 방향이 바뀌는 부분 로직을 나는 각 방향마다 for문 4개로 단순하게 나눠버렸다면, 레퍼런스 코드는 각 방향에 명칭을 부여하고, 방향 순환이 반복된다는 점에 착안하여 모듈러 연산을 사용해서 구현했다.

 

 어떻게 처음부터 깔끔한 코드를 짤까? 계속 눈으로 익히는 수밖에 없다. 남이 작성한 코드를 많이 보면서 더 좋은 코드를 구현하는 방법을 체화하려고 노력하자. 자연어 공부가 인풋이 많아질수록 실력이 느는 것처럼 코딩도 마찬가지다. 좋은 코드를 많이 접하면 접할수록 아키텍처 설계에 대한 눈이 점점 틔일 것이다. 이번 토이 문제만 해도 벌써 생각하지 못했던 설계법을 배웠으니까!

 

 그리고 result 를 문자열로 선언 후 순회 요소 값을 문자열 합치기 연산해주면 join 함수를 쓸 필요도 없다! 습관처럼 배열로 만들어 push를 해줬는데, 굳이 result를 배열로 만들어서 push할 이유가 없었다. 자바스크립트는 + 연산자로 바로 문자열을 합칠 수 있는 것도 알고 이전까지는 이를 유용하게 사용했었는데 이번엔 왜 순간적으로 생각해내지 못했는지...