JavaScript로 spiral traversal 구현하기

문제

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

수도코드

아래와 같이 layer 개념으로 풀 수 있겠다고 생각했고, 그럴려면 재귀함수로 문제를 접근해야하지 않을까 생각했다.

// 재귀의 탈출 조건: matrix.length===0 or matrix.length===1 
// 한 개의 layer만 생각했을 때 4번의 for문을 돌려서 상 우 하 좌 순서로 문자열을 누적해나간다
// 한 레이어를 벗겨낸 안쪽 행렬을 만들어 재귀함수의 인자로 넣어준다.

코드로 나타내보면

하나의 레이어는 아래와 같은 규칙으로 문자열을 누적하였다. 총 for문을 네 번 작성하였는데 다른 효율적인 방법이 있을지 생각해봐야겠다.

  for(let i=0; i<matrix[0].length-1; i++){
    str = str+matrix[0][i]
  }
  for(let i=0; i<matrix.length-1; i++){
    str = str+matrix[i][matrix[0].length-1]
  }
  for(let i=matrix[0].length-1; i>0; i--){
    str = str+matrix[matrix.length-1][i]
  }
  for(let i=matrix.length-1; i>0; i--){
    str = str+matrix[i][0]
  }

전체 코드는 아래와 같다.

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

  let str = ''
  // matrix.length===0 or matrix.length===1 --> 재귀 종료조건이다!
  if(matrix.length===0){
    return ''
  }
  if(matrix.length===1){
    for(let i=0; i<matrix[0].length; i++){
      str = str+matrix[0][i]
    }
    return str;
  }
  
  //아래는 '한 바퀴' 돌아서 문자열로 누적하는 것  
  for(let i=0; i<matrix[0].length-1; i++){
    str = str+matrix[0][i]
  }
  for(let i=0; i<matrix.length-1; i++){
    str = str+matrix[i][matrix[0].length-1]
  }
  for(let i=matrix[0].length-1; i>0; i--){
    str = str+matrix[matrix.length-1][i]
  }
  for(let i=matrix.length-1; i>0; i--){
    str = str+matrix[i][0]
  }
  //한 바퀴 떼어내고 안의 작은 행렬을 만드는 것
  let smallMatrix = matrix.slice(1, matrix.length-1)
  for(let i=0; i<smallMatrix.length; i++){
    smallMatrix[i] = smallMatrix[i].slice(1, smallMatrix[i].length-1)
  }
  //작은 행렬 재귀~
  return str+spiralTraversal(smallMatrix);
};