Spiral Matrix 회오리 모양으로 2차원 배열 탐색하기 (구현)

김민아·2023년 1월 17일
1

54. Spiral Matrix

54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order. e.g. [1,2,3,4,8,12,11,10,9,5,6,7]

풀이

좌표를 잡을 때 면적이 아닌 바둑판처럼 점을 기준으로 보면 이해가 쉽다. 회오리 모양으로 반복하기 위해서 다음 규칙을 반복한다.

  1. 이동: 왼쪽에서 오른쪽
  2. 이동: 위에서 아래
  3. 이동: 오른쪽에서 왼쪽
  4. 이동: 아래에서 위

잘 생각해보면 모든 좌표가 한 지점에 만날 때까지 규칙이 반복되는데, result에 범위만큼 숫자를 추가하고 좌표 범위를 좁혀준다. 범위는 top, left는 0이며, right은 matrix[n].length-1, bottom은 matrix.length-1이다.

만약 5*5 matrix를 예를 들면 먼저,
좌표 범위가 역으로 진행되지 않도록 while 조건을 추가하고.

  1. left(0) ~ right(4)까지 [1, 2, 3, 4, 5]를 추가한다.
    • 첫 행을 제외하기 위해 top(0)좌표를 +1 해준다. top(1)
  2. top(1) ~ bottom(4)까지 [... 10, 15, 20, 25]를 추가한다.
    • 우측 열을 제외하기 위해 right(4)를 -1 해준다. right(3)
  3. right(3) ~ left(0)까지 [24, 23, 22, 21]를 추가한다.
    • 끝 행을 제외하기 위해 bottom(4)좌표를 -1 해준다. bottom(3)
  4. bottom(3) ~ top(1)까지 [16, 11, 6]를 추가한다.
    • 좌측 열을 제외하기 위해 left(0)을 +1 해준다.
  • 반복...

테스트를 해보면 중간에 while 조건이 한번 더 추가 되었는데,
왼쪽에서 오른쪽 방향으로 마지막 조건에 부합할 때 아래 남은 방향의 코드를 진행하면 right가 left보다 작아지면서 역으로 진행이 되기 때문이었다.

코드

var spiralOrder = function(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  
  let [top, left, right, bottom] = [0, 0, cols - 1, rows - 1]
  let result = [];

  while (left <= right && top <= bottom) {
    // left to right
    for (let i = left; i <= right; i++) {
      result.push(matrix[top][i])
    }
    top++

    // top to bottom
    for (let i = top; i <= bottom; i++) {
      result.push(matrix[i][right])
    }
    right--

    // 여기서 while 조건을 충족할 경우, 빠져나올 수 있도록 
    if (left <= right && top <= bottom) {
      // right to left
      for (let i = right; i >= left; i--) {
        result.push(matrix[bottom][i])
      }
      bottom--
  
      // bottom to up
      for (let i = bottom; i >= top; i--) {
        result.push(matrix[i][left])
      }
      left++
    }
  }
  return result
};

const testCase1 = [[1,2,3], [4,5,6], [7,8,9]]
const testCase2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
const testCase3 = [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]]

console.log(spiralOrder(testCase3))

출처

  • LeetCode에서 참고한 링크 (를 잃어버렸어요...🥹)

0개의 댓글