Leetcode Python - 59. Spiral Matrix II

Leetcode #59 - Spiral Matrix II

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. matrix을 집중적으로 풀어보겠습니다.

리트코드의 문제 59 ‘Spiral Matrix II’을 파이썬으로 풀어 보도록 하겠습니다.

이 문제도 이전 Spiral Matrix를 참고하여 풀 수 있습니다. 포인트는 row_begin, col_begin, row_end, col_end를 선언하여 진행해 나가면 됩니다.

전체 코드는 아래와 같습니다.

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        if n == 1:
            return [[1]]
        
        ret = [[0]*n for i in range(n)]
        
        row_begin = 0
        col_begin = 0
        row_end = n-1
        col_end = n-1
        
        value = 1
        while row_begin <= row_end and col_begin <= col_end:
            
            for i in range(col_begin, col_end+1):
                ret[row_begin][i] = value
                value += 1
            row_begin += 1
            
            for i in range(row_begin, row_end+1):
                ret[i][col_end] = value
                value += 1
            col_end -= 1
            if col_begin <= col_end:
                for i in range(col_end, col_begin-1, -1):
                    ret[row_end][i] = value
                    value += 1
                row_end -= 1
            if row_begin <= row_end:
                for i in range(row_end, row_begin-1, -1):
                    ret[i][col_begin] = value
                    value += 1
                col_begin += 1
            
        return ret

시간복잡도는

• O(n^2) : 모든 element를 방문

공간복잡도는

• O(n^2) : 전체 크기