Today I Learned

오늘도 코테코테

Spiral Matrix

leetcode 54번. https://leetcode.com/problems/spiral-matrix/description/

문제

Given an m x n matrix, return all elements of the matrix in spiral order.

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

풀이 과정

• 주어진 2D 배열을 나선형으로 순회하는 문제다. 상, 하, 좌, 우 네 방향으로 순회하면서 배열의 원소를 방문해야 한다.

1. 주어진 배열을 나선형으로 순회하기 위해서는 시작 위치(rb, cb)와 끝 위치(re, ce)를 설정하고, 각 방향으로 순회하면서 결과를 리스트에 추가한다.
   순회가 끝날 때마다 시작 위치와 끝 위치를 조정하여 계속해서 나선형으로 순회할 수 있도록 한다.

2. 우측 방향으로 순회하면서 rb 증가, 아래로 순회하면서 ce를 감소, 왼쪽 순회하면서 re를 감소 (단, 순회할 행의 개수가 남아있을 때만 수행), 위로 순회하면서 cb 증가시킵니다. (단, 순회할 열의 개수가 남아있을 때만 수행)

이렇게 하면 배열을 나선형으로 순회할 수 있다.

Java 코드

import java.util.ArrayList;
import java.util.List;


class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      return result;
    }

    int rb = 0;
    int re = matrix.length - 1;
    int cb = 0;
    int ce = matrix[0].length - 1;

    while (rb <= re && cb <= ce) {
      // 오른쪽으로
      for (int j = cb; j <= ce; j++) {
        result.add(matrix[rb][j]);
      }
      rb++;

      // 밑으로
      for (int j = rb; j <= re; j++) {
        result.add(matrix[j][ce]);
      }
      ce--;

      // 왼쪽으로
      if (rb <= re) {
        for (int j = ce; j >= cb; j--) {
          result.add(matrix[re][j]);
        }
      }
      re--;

      // 위로
      if (cb <= ce) {
        for (int j = re; j >= rb; j--) {
          result.add(matrix[j][cb]);
        }
      }
      cb++;
    }

    return result;
  }
}