72일 (54. Spiral Matrix) matrix, 접근방법과 공간개선필요

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

 

 

 

- 접근방법

배열의 크기가 1일때만 예외처리를 하고, 나머지 크기의 모든 배열을 순회할 때는 각각의 방향을 순회할 때마다 원소의 개수를 세었다.

배열을 4방향으로 한바퀴 순회를 하였다면 배열의 시작점 i,j를 각각 +1 끝점인 length-1을  -1씩 조절하여 논리적으로 안쪽배열을 순회할 수 있게 하였다.

그리고 배열을 m*n번 순회하였을 때 순회가 종료되게 하였다.

 

 

- m*m배열과 m*n 배열 둘의 공통된 종료조건을 명확히 찾지 못하였다.

 위 그림을 예로 들면, m*m배열의 시작점을 +1, 끝점을 -1로 범위조건을 설정하면 m*m의 배열의 경우 안쪽배열이 종료조건때문에 순회가 불가능하다. 

(왜냐하면 처음의 순회횟수 2번이지만 한바퀴 돌았을때, 시작점을+1 끝점을-1하면 범위는 -2가 줄어든다. 그렇다면 파란색화살표 순회시 원소가 1개 남았음에도 순회불가...)

 그리고 m*n배열일때도 종료조건을 다르게 줘야 제대로 동작된다..

  

 

 

-  코드

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int colStart = 0;
        int rowStart = 0;
        int rowEnd = matrix.length;
        int colEnd = matrix[0].length;
        List<Integer> list = new ArrayList<>(rowEnd * colEnd);
        int cnt = rowEnd * colEnd; // matrix배열의 크기만큼만 원소를 list에 넣을 것이다.

        while(rowStart < rowEnd && colStart < colEnd) {

            if((colEnd-1 == colStart && rowEnd-1 == rowStart)) { // 배열의 크기가 1일때
                list.add(matrix[rowStart][colStart]);
                cnt--;
            }

            for(int j = colStart; j < colEnd-1; j++) { // 1방향 순회
                if(cnt > 0) {
                    list.add(matrix[rowStart][j]);
                    cnt--;
                }
            }

            for(int i = rowStart; i < rowEnd-1; i++) { // 2방향 순회
                if(cnt > 0) {
                    list.add(matrix[i][colEnd-1]);
                    cnt--;
                }
            }

            for(int j = colEnd-1; j > colStart; j--) { // 3방향 순회
                if(cnt > 0) {
                    list.add(matrix[rowEnd-1][j]);
                    cnt--;
                }
            }

            for(int i = rowEnd-1; i > rowStart; i--) { // 4방향 순회
                if(cnt > 0) {
                    list.add(matrix[i][colStart]);
                    cnt--;
                }
            }

            // 논리적을 배열의 시작점을 +1, 끝나는 지점을 -1 조정한다.
            colStart++;
            rowStart++;
            rowEnd--;
            colEnd--;
        }

        return list;
    }
}

 

문제의 접근방법에 대해서도 개선이 필요하고, 변수사용을 줄이는 방법에 대해서도 개선이 필요하다.

(스스로 느끼기에 당연히 좋은 방법이 아니고, 공간복잡도도 높다.)

 

 

 

 

https://leetcode.com/problems/spiral-matrix/

Spiral Matrix - LeetCode