[LeetCode][Python3] 54. Spiral Matrix

Problem :

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

My Solution :

class Solution:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

ret = []

if not matrix:

return ret

left, right = 0, len(matrix[0])-1

top, bottom = 0, len(matrix)-1

while left <= right and top <= bottom:

for col in range(left, right+1):

ret.append(matrix[top][col])

for row in range(top+1, bottom+1):

ret.append(matrix[row][right])

if left < right and top < bottom:

for col in range(right-1, left, -1):

ret.append(matrix[bottom][col])

for row in range(bottom, top, -1):

ret.append(matrix[row][left])

top += 1

right -= 1

bottom -= 1

left += 1

return ret

Comment :

위 풀이는 top, right, bottom, left 순서대로 순회 후 layer를 한칸씩 안쪽으로 들어가는 방식인데, index out of range를 엄청나게 맞아가며 수정하였다 ㅠㅠ 결국 아래 그림의 왼쪽이 아닌 오른쪽처럼 순회하고 (누락 방지), top, right 순회 후 한번 멈춰서 bottom, left 진행 여부를 검사해야 함을 알게 되었다. (중복 방지)

※ top right가 빨강이건 노랑이건 그건 중요하지 않다. bottom left 역시 초록이건 파랑이건 중요하지 않다. 중요한건 상반기 순회시 top left와 bottom right를 포함해서 순회 후 나머지 하반기 순회 여부를 결정해야 누락이 발생하지 않는다는 것이다.

아래 풀이는 matrix를 반 시계 방향으로 rotate 시키면서 top row를 추출하는 트릭이다.

My Solution 2 :

class Solution:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

ret = []

while matrix:

ret.extend(matrix.pop(0))

matrix = list(zip(*matrix))[::-1]

return ret