[LeetCode] 59. Spiral Matrix II

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

Spiral Matrix II - LeetCode

문제 유형 : 나선형 행렬

문제 난이도 : Medium

 

문제

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

 

양의 정수 n이 주어지면 n*n의 이차원 배열을 만들고, 1부터 n^2까지의 숫자를 나선형으로 순회하도록 요소를 배치해라.

(1 <= n <= 20)

 

풀이

Spiral Matrix I에서의 로직과 같다. 이번에는 2차원 배열의 값을 1로 초기화해주고, 한 칸씩 순회할 때 마다 1씩 더 큰 숫자를 더해주면 된다.

 

코드(C++)

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix (n, vector<int>(n, 1));
        if(n == 1){
            return matrix;
        }
        int goal = n * n;
        int col = 0;
        int row = 0;
        int cnt = 1;
        int loop = 0;

        while(cnt < goal){
            row++;
            for(int i = row; i < n; i++){
                matrix.at(col).at(i) += cnt;
                cnt++;
            }
            if(cnt >= goal) break;
            col++;
            row = n-1;
            for(int i = col; i < n; i++){
                matrix.at(i).at(row) += cnt;
                cnt++;
            }
            if(cnt >= goal) break;
            row--;
            col = n-1;
            n--;
            for(int i = row; i >= loop; i--){
                matrix.at(col).at(i) += cnt;
                cnt++;
            }
            if(cnt >= goal) break;
            col--;
            row = loop;
            loop++;
            for(int i = col; i >= loop; i--){
                matrix.at(i).at(row) += cnt;
                cnt++;
            }
            col = loop;
        }
        return matrix;
    }
};

O(N*2)의 시간복잡도를 가진다.