885. Spiral Matrix III

[zeikar]

Problem link

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

Problem Summary

지정된 위치에서 배열을 spiral (달팽이) 모양으로 순회할 때 위치를 출력하는 문제.

Solution

일단 나는 202 x 202의 가상 보드를 만들고 무식하게 달팽이를 만들었다... (사람이 보고 적는 것처럼 수가 없으면 앞으로 가고 있으면 방향을 트는 방식). 시간복잡도는 O(RC)

그런데 달팽이 만들 때의 규칙을 쓰면 더 간단하게 풀 수 있다. 달팽이 만들 때는 이동 횟수가 1, 1, 2, 2, 3, 3... 처럼 증가하는 것... 이러면 가상 보드를 만들 필요 없이 좌표만 범위 안에 들어오는지만 보고 출력할 수 있다.

해당 방법은 에디토리얼 및 솔루션 등 참고.

Source Code

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        board = [[0] * 202 for _ in range(202)]
        x = 101
        y = 101
        minX = x - rStart
        maxX = x + rows - rStart - 1
        minY = y - cStart
        maxY = y + cols - cStart - 1

        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        d = 3
        cnt = 1
        ans = []

        while len(ans) < rows * cols:
            board[x][y] = cnt
            if x >= minX and x <= maxX and y >= minY and y <= maxY:
                ans.append([x - 101 + rStart, y - 101 + cStart])
                cnt += 1

            nx = x + dir[(d+1) % 4][0]
            ny = y + dir[(d+1) % 4][1]
            if board[nx][ny] == 0:  # ok
                x = nx
                y = ny
                d = (d+1) % 4
            else:
                x = x + dir[d][0]
                y = y + dir[d][1]

        return ans