Algorithm problem-23

1. 문제

• 2차원 M x N 매트릭스를 나선형으로 순회하여 string으로 이어 리턴하라
• [0][0]에서 출발하여 오른쪽으로 순회한다

2. 시도

• 문자열로 리턴해야 하니까, 결과를 빈 문자열에 더해줘서 그 값을 리턴하자
• while문을 이용하고, 배열의 값을 빼내어 빈 문자열에 순서대로 더해주면서 순회
• 0이 될 때까지 돌리고, 위, 오른쪽, 아래(역), 왼쪽(역)순으로 순회시키면서
• 위와 아래값은 전부 빼내어 담아줄거니까 마지막에 삭제해주면
• 값이 아직 남아있는 경우, 삭제하고 남아있는 배열이 0번으로 올라가니 다시 순회하겠지
• qwert
• yuiop
• asdfg
• hjklz
• xcvbn 을 1번 순회한다고 하면
• uio
• sdf
• jkl 이 남게 된다고 예상함

3. 수도코드

const spiralTraversal = function (matrix) {
  // 결과를 담을 빈 문자열 선언
  let result = '';
  // 요소를 다 빼거나 빈 배열을 받으면 결과를 리턴시키고
  //if (matrix.length === 0) {return result;}
  // while을 사용하면 될까?
  while (matrix.length > 0) {
    let max = matrix.length - 1
    // 위, 오른쪽, 아래(역순), 왼쪽(역순)
    // 순서대로 순회하면서 요소를 빼서 결과에 담고, 남아있으면 다시 돌리고
    // 위, 다 빼서 넣을거니까 while로 돌려도 되려나
    while (matrix[0].length > 0) {
      result = result + matrix[0].shift();
    }
    // 오른쪽, 0번은 다 뺐으니까 0번 제외하고 맨 끝도 제외
    for (let i = 1; i < matrix.length - 1; i++) {
      result = result + matrix[i].pop()
    }
    // 아래, 다 빼서 넣을거니까 while
    while (matrix[max].length > 0) {
      result = result + matrix[max].pop()
    }
    // 왼쪽, 0,끝번은 다 뺏으니까 제외하고 
    for (let i = matrix.length - 2; i > 0; i--) {
      result = result + matrix[i].shift()
    }
    console.log(matrix)
    // 다 빼고 나면, 빈 배열은 삭제해줘야 하니까
    matrix.shift()
    matrix.pop()
  }
  return result;
};
// 너무 무식하게 푼거 같긴 하다..
// 최대 길이를 찾아서 저장는 안해도 될 듯?
// 0idx는 전부
// for문으로 1번부터 최대 전까지의 끝 인덱스만 뽑아내고
// 끝번idx는 역순으로 전부
// 최대 전부터 1번까지의 0번 인덱스를 뽑고
// 다시 0번과 끝번 제외하고 다시 반복
// 쉬프트, 팝 등 메소드를 사용하면 될 듯
// 남은 요소가 있는 동안 계속 돌아야 함

4. 레퍼런스

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