Leetcode 54. Spiral Matrix

링크는 https://leetcode.com/problems/spiral-matrix/description/

 

# 문제이해

정수로 된 숫자 배열이 주어지면, 우 -> 하 -> 좌 -> 상 방향으로 돌면서, 숫자 순서를 아웃풋 하는 방식.

 

# 생각해본 방법

모든 숫자를 하나하나 완전 탐색해야 하지 않을까 생각

요론식의 수도 코드를 생각했다.

checked = [[]] 
direction [right, down, left, right] # right(0,1)
cnt = 0
direction[cnt % len(direction)]
x, y = 0, 0 # start
while cnt:
    dx, dy = direction[cnt % len(direction)]
    nx += dx
    ny += dy
    if 0 <= nx <= m and 0 <= ny <=n and checked[nx][ny]:
       ...
    else:
        cnt += 1

 

 

# Try 1. 성공

34ms Beats 67.10%

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        answer = []
        checked = [[0] * n for _ in range(m)]
        right, down, left, up = (0, 1), (1,0), (0, -1), (-1, 0)
        direction = [right, down, left, up]
        x, y = 0, 0
        cnt = 0

        # start 
        answer.append(matrix[0][0])
        checked[0][0] = 1

        while len(answer) != m*n:
            dy, dx = direction[cnt%len(direction)]
            nx = x + dx
            ny = y + dy
            if (0 <= nx < n and 0 <= ny < m) and checked[ny][nx] == 0:
                answer.append(matrix[ny][nx])
                checked[ny][nx] = 1
                x, y  = nx, ny
            else:
                cnt += 1
        return answer

 

 

# 생각해본 방법 2

python 이니까, stack/pop 을 잘 사용하면 쉽게 갈 수 있지 않을까 싶었다. right 일때는 가장 위의 배열 전체를 쭉 훑으니 pop 해주고, 

down 은 배열들의 가장 마지막 원소를 pop 해주는 식으로 stack / pop 구조를 이용해보기로

 

# Try 1. 성공

Runtime - 26ms Beats96.67%

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        length = len(matrix[0]) * len(matrix)
        answer = []
        direction = ['right', 'down', 'left', 'up']
        cnt = 0
        while len(answer) != length:
            if direction[cnt%len(direction)] == 'right':
                arr = matrix.pop(0)
                answer.extend(arr)
            elif direction[cnt%len(direction)] == 'down':
                for arr in matrix:
                    answer.append(arr.pop())
            elif direction[cnt%len(direction)] == 'left':
                arr = matrix.pop()
                answer.extend(arr[::-1])
            else: #up
                tmp = []
                for arr in matrix:
                    tmp.append(arr.pop(0))
                answer.extend(tmp[::-1])
            cnt += 1
        return answer

로 풀이했는데 Runtime 이 빨라졌다 신기하네.