[Medium] 54. Spiral Matrix (Microsoft)

#문제 설명

Leetcode 54번 문제는 m x n matrix 가 주어진다. matrix의 값은 1부터 n까지의 정수로 채워진다. 정수의 순서는 matrix에 나션형 모양으로 나열된다. 우리는 이 matrix를 나선형 (matrix[0][0] 에서 시작해서 오른쪽끝, 맨 아래, 맨 왼쪽, 위로를 matrix의 전체가 커버 될때까지 반복한다). 이 과정에서 각 index를 지날때마다, index에 있는 정수 값들을 list에 add해주면 된다, 그리고 그 list를 return해주면 된다.

#문제 풀이

이 문제는 총 네가지 (오른쪽, 아래, 왼쪽, 위) traverse하는 경우가있기때문에, 그 index들을 tracking하는 variable를 만들고, 그 varible들 (matrix index)을 증가 (오른쪽, 위) 또는 감소 (왼쪽, 아래) 시키면서 나선형으로 matrix를 traverse하는 방법이다.

 

처음 index, matrix[0][0]부터 시작해서 오른쪽 traverse후 rowBegin 증가시키고,  아래 traverse후 colEnd 감소, 왼쪽 traverse후  rowEnd 감소, 마지막으로 위로 이동하여 colBegin을 증가시킴. 마지막으로 위로 traverse하고 colBegin을 증가시킨다. 모든 index가 커버 될때 까지 이런식으로 반복한다.

 

이 풀이에서 유일하게 까다로운 부분은 왼쪽이나 위로 이동할 때 중복을 방지하기 위해 행이나 열이 계속 존재하는지 확인해야 한다는 것이다.

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> res = new ArrayList<Integer>();
        
        if (matrix.length == 0) {
            return res;
        }
        
        int rowBegin = 0;
        int rowEnd = matrix.length-1;
        int colBegin = 0;
        int colEnd = matrix[0].length - 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            // Traverse Right
            for (int j = colBegin; j <= colEnd; j ++) {
                res.add(matrix[rowBegin][j]);
            }
            rowBegin++;
            
            // Traverse Down
            for (int j = rowBegin; j <= rowEnd; j ++) {
                res.add(matrix[j][colEnd]);
            }
            colEnd--;
            
            if (rowBegin <= rowEnd) {
                // Traverse Left
                for (int j = colEnd; j >= colBegin; j --) {
                    res.add(matrix[rowEnd][j]);
                }
            }
            rowEnd--;
            
            if (colBegin <= colEnd) {
                // Traver Up
                for (int j = rowEnd; j >= rowBegin; j --) {
                    res.add(matrix[j][colBegin]);
                }
            }
            colBegin ++;
        }
        
        return res;
    }
}