리트코드 Spiral Matrix 풀이

1번째 풀이

• 문제 풀이 개념 :

나선형으로 돌아갈 때 answer에 입력한 값을 중복체크한다. 만약 check[x][y]가 0이면 한번도 들어가지 않은 것으로 판단하고 진행한다. 만약 check[x][y]가 1일 경우 중복으로 판단하고 다음 스탭으로 넘어간다.

우측, 아래, 좌측, 위 4가지 방향으로 돌면서 각각의 인덱스가 범위가 넘어가면 방향을 바꿔서 진행한다.

이 풀이 법은 timeout이 났다. 그래서 새로운 방법을 고안해냈다.

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> answer = new ArrayList<>();

        int[][] check = new int[m][n];

        int index = 0;

        int x = 0;
        int y = 0;

        int delta = 0;

        while (index<=m*n) {
            if (delta==0) {
                while (y<n && check[x][y]==0) {
                    answer.add(matrix[x][y]);
                    check[x][y] = 1;
                    y++;
                    index++;   
                }
                delta = (delta +1)%4;
                y--;
                x++;
            }

            else if (delta==1) {
                while (x<m && check[x][y]==0) {
                    answer.add(matrix[x][y]);
                    check[x][y] = 1;                    
                    x++;
                    index++;                       
                }
                delta = (delta +1)%4;
                x--;
                y--;

            }

            else if (delta==2) {
                while (y>=0 && check[x][y]==0) {
                    answer.add(matrix[x][y]);
                    check[x][y] = 1;
                    y--;
                    index++;   
                }
                delta = (delta +1)%4;
                y++;
                x--;
            }
            
            else {
                while (x>=0 && check[x][y]==0 ) {
                    answer.add(matrix[x][y]);
                    check[x][y] = 1;
                    x--;
                    index++;   
                }
                delta = (delta +1)%4;
                x++;
                y++;
            }

            
        }
        return answer;
    }
}

두번째 풀이

• 풀이 개념 :

이 풀이법은 중복 체크하는 대신에 for문을 활용해 4가지 방향에 대한 시작 인덱스를 방향이 바뀔 때 마다 수정해서 나선형으로 도는 코드이다. 마치 이전에 올린 대각선으로 왔다갔다 하는 문제에서 아래로 가는 인덱스 위로 가는 인덱스의 변화를 주었던 것과 비슷하다고 볼 수 있다.

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

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

        int m = matrix.length;
        int n = matrix[0].length;

        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        int direction = 0;

        while (top <= bottom && left <= right) {
            if (direction == 0) {
                for (int i = left; i <= right; i++) {
                    answer.add(matrix[top][i]);
                }
                top++;
            } else if (direction == 1) {
                for (int i = top; i <= bottom; i++) {
                    answer.add(matrix[i][right]);
                }
                right--;
            } else if (direction == 2) {
                for (int i = right; i >= left; i--) {
                    answer.add(matrix[bottom][i]);
                }
                bottom--;
            } else if (direction == 3) {
                for (int i = bottom; i >= top; i--) {
                    answer.add(matrix[i][left]);
                }
                left++;
            }
            direction = (direction + 1) % 4;
        }
        return answer;
    }
}