[LeetCode] 54. Spiral Matrix

Problem

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

Example 1:

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

Example 2:

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]

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

---

Solution

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<Integer>();
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while (result.size() < matrix.length * matrix[0].length) {
            for (int i = left; i <= right && result.size() < matrix.length * matrix[0].length; i++)
                result.add(matrix[top][i]);

            for (int i = top + 1; i <= bottom - 1 && result.size() < matrix.length * matrix[0].length; i++)
                result.add(matrix[i][right]);

            for (int i = right; left <= i && result.size() < matrix.length * matrix[0].length; i--)
                result.add(matrix[bottom][i]);

            for (int i = bottom - 1; top + 1 <= i && result.size() < matrix.length * matrix[0].length; i--) 
                result.add(matrix[i][left]);

            left++; right--; top++; bottom--; 
        } return result;
    }
}

Explanation

• 결과 반환을 위한 리스트를 선언한다.

  List<Integer> result = new ArrayList<Integer>();
  

• matrix[0][0]부터 오른쪽에 위치한 요소들을 차례대로 리스트에 넣는 for 반복문을 작성한다.

  for (int i = 0; i <= matrix[0].length; i++)
    result.add(matrix[0][i]);
  

• Spiral 형태로 요소들을 리스트에 넣으려면 위와 같은 과정이 3번 더 필요하기 때문에 for 반복문 3개를 추가로 작성한다.
• 이때 이미 리스트에 들어있던 요소가 다시 들어가지 않도록 for 반복문 내의 변수 i의 초기화와 조건식에 유의하여 작성한다.

for (int i = 1; i <= matrix.length; i++)
    result.add(matrix[i][matrix[0].length]);

for (int i = matrix[0].length - 2; 0 <= i; i--)
    result.add(matrix[matrix.length][i]);

for (int i = matrix.length - 2; 1 <= i; i--) 
    result.add(matrix[i][0]);

• 위 과정을 반복하기 위해 반복문을 사용해야 하는데, 2차원 배열 matrix의 크기를 알 수 없으므로 while 반복문으로 4개의 for 반복문을 감싸준다.
• 다시 for 반복문이 수행될 때 for 반복문 속의 변수 i의 초기화와 조건식이 변경되어야 하는데 이를 쉽게 하기 위해서 2차원 배열 속 요소들의 인덱스를 참조하는 변수 top, bottom, left, right를 선언한다.
• while 반복문이 진행될 때마다 위 4개의 변수 값이 변경될 수 있도록 증감식을 작성한다.

  int top = 0;
  int bottom = matrix.length - 1;
  int left = 0;
  int right = matrix[0].length - 1;
  while (result.size() < matrix.length * matrix[0].length) {
    for (int i = left; i <= right && result.size() < matrix.length * matrix[0].length; i++)
        result.add(matrix[top][i]);
  
    for (int i = top + 1; i <= bottom - 1 && result.size() < matrix.length * matrix[0].length; i++)
        result.add(matrix[i][right]);
  
    for (int i = right; left <= i && result.size() < matrix.length * matrix[0].length; i--)
        result.add(matrix[bottom][i]);
  
    for (int i = bottom - 1; top + 1 <= i && result.size() < matrix.length * matrix[0].length; i--) 
        result.add(matrix[i][left]);
  
    left++; right--; top++; bottom--; 
  }
  

• 만들어진 리스트를 반환한다.

  return result;