Spiral Matrix

Q: Spiral Matrix의 시간 및 공간 복잡도는 얼마인가요?

두 접근 방식 모두 각 값을 한 번씩 읽으므로 시간 복잡도는 O(m × n) 이며, 답에 모든 값이 포함되기 때문에 이보다 더 나은 해결 방법은 없습니다. 네 개의 경계를 사용해 층을 벗겨 내는 방식은 답을 제외하면 O(1) 의 추가 메모리를 사용합니다. 막히면 방향을 바꾸며 이동하는 방식은 읽은 셀을 기억하기 위해 O(m × n) 크기의 격자를 사용합니다.

Q: 행렬을 읽는 대신 나선형 순서로 채우려면 어떻게 해야 할까요?

같은 네 개의 경계와 같은 네 개의 변을 사용하되, 읽는 대신 씁니다. 1 에서 시작하는 카운터를 유지하고, 각 셀을 지나갈 때마다 그 값을 저장하며 1씩 더합니다. n × n 행렬의 경우 카운터는 n² 에서 끝나며, 위의 첫 번째 예시는 4 × 3 격자에 이렇게 적용한 결과입니다.

보통수학과 시뮬레이션 배열과 문자열

+10

m개의 행과 n개의 열로 이루어진 정수 행렬이 행들의 목록으로 주어집니다. 모든 값을 나선형 순서로 반환하세요.

왼쪽 위 모서리에서 시작해 맨 위 행을 따라 오른쪽으로 이동한 다음, 맨 오른쪽 열을 따라 아래로 이동하고, 맨 아래 행을 따라 왼쪽으로 이동한 뒤, 맨 왼쪽 열을 따라 위로 이동하세요. 모든 값을 정확히 한 번씩 읽을 때까지 시계 방향으로 안쪽을 향해 계속 돌며 이동하세요.

함수

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: 길이가 같은 행들의 목록으로 이루어진 정수 격자
반환값integer-array: 왼쪽 위 모서리에서 시작하여 시계 방향 나선 순서로 행렬의 모든 값을

제약 조건

1 ≤ m, n ≤ 80이며, 여기서 m = matrix.length이고 n = matrix[i].length입니다.
모든 행의 길이는 동일하게 n입니다.
-100 ≤ matrix[i][j] ≤ 100

예제

입력: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
출력: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
설명: 값은 나선형을 따라 증가합니다. 바깥쪽 고리는 위쪽을 따라 1, 2, 3, 오른쪽을 따라 아래로 4, 5, 6, 아래쪽을 따라 되돌아가며 7, 8, 왼쪽을 따라 위로 9, 10을 읽습니다. 안쪽 층은 하나의 열로, 위에서 아래로 한 번 읽습니다: 11, 12.

입력: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
출력: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
설명: 바깥쪽 고리는 7, 1, 5, 3을 제공하고, 오른쪽을 따라 아래로 6, -1, 아래쪽을 따라 되돌아가며 4, 0, 8, 왼쪽을 따라 위로 2를 제공합니다. 남은 것은 왼쪽에서 오른쪽으로 한 번 읽는 단일 행 9, -4입니다.

제출 시 숨은 테스트 +15개

후속 질문

대신 왼쪽 위 모서리에서 시작해 왼쪽 열을 먼저 따라 내려가며 반시계 방향으로 값을 반환할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

여기에는 특별한 수학적 기교가 필요하지 않습니다. 문제는 장부 정리이며, 해법이 무너지는 지점도 바로 그 장부 정리입니다. 각 모서리는 두 번이 아니라 한 번만 읽어야 하고, 가장 안쪽 층은 한 행이나 한 열만 남을 수 있으며, 이때 한 바퀴를 완전히 돌면 같은 값을 다시 지나게 됩니다. 막히면 오른쪽으로 돌고 자신이 읽은 셀을 기억하는 로봇처럼 이동할 수 있습니다. 또는 추가 메모리 없이 네 개의 경계를 줄여 가며 한 번에 한 겹씩 행렬을 벗겨 낼 수도 있습니다.

막히면 걷다가 오른쪽으로 회전하기

핵심 아이디어

오른쪽을 향하고 있는 왼쪽 위 칸의 보행자를 떠올려 보세요. 보행자는 자신이 있는 칸을 읽고 앞으로 한 칸 이동하려고 합니다. 그 칸으로 이동하면 행렬을 벗어나거나 이미 읽은 칸에 도달하는 경우, 오른쪽(오른쪽, 아래쪽, 왼쪽, 위쪽, 다시 오른쪽)으로 방향을 틀어 대신 그쪽으로 이동합니다. 이 규칙이 나선형 경로를 만듭니다. 행렬의 가장자리가 첫 번째 바퀴를 막고, 지금까지 읽은 칸들이 그 이후의 바퀴마다 벽 역할을 합니다.

방향은 두 개의 작은 배열 dr = [0, 1, 0, -1]과 dc = [1, 0, -1, 0]의 인덱스 d로 유지하면, 오른쪽으로 방향을 트는 동작은 d = (d+1) % 4가 됩니다. 행렬과 같은 크기의 불리언 격자 seen을 유지하세요. 첫 번째 예시에서 보행자는 1, 2, 3을 읽고 오른쪽 가장자리에 도달해 아래쪽으로 방향을 틀어 4, 5, 6을 읽습니다. 그런 다음 왼쪽으로 방향을 틀어 7, 8을 읽고 위쪽으로 방향을 틀어 9, 10을 읽습니다. 10 위에는 이미 읽은 1이 있으므로 오른쪽으로 방향을 틀어 11로 이동합니다. 11 오른쪽에는 이미 읽은 4가 있으므로 아래쪽으로 방향을 틀어 12로 이동합니다.

루프를 정확히 m × n번, 각 칸당 한 번씩 실행하면 끝을 감지할 필요가 없습니다. 마지막 칸을 읽은 뒤 보행자는 벽을 향할 수도 있지만, 더는 이동하지 않습니다. 각 칸을 한 번씩 읽으므로 시간 복잡도는 O(m × n)입니다. seen 격자는 O(m × n)의 추가 메모리를 사용하며, 다음 접근 방식에서는 이를 없앱니다.

알고리즘

seen 격자의 모든 값이 false인 상태에서 행 0, 열 0에서 오른쪽을 바라보며 시작합니다.
m × n번 반복합니다. 현재 값을 추가하고 해당 셀을 방문한 것으로 표시합니다.
현재 방향으로 다음 셀을 계산합니다. 행렬 범위를 벗어나거나 이미 방문한 셀이라면 오른쪽으로 방향을 돌린 뒤 다시 계산합니다.
해당 셀로 이동합니다.
추가한 순서대로 값을 반환합니다.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

네 개의 경계로 층을 벗겨내기

핵심 아이디어

나선은 중첩된 고리들의 집합입니다. 현재 고리를 네 개의 경계로 나타냅니다. 행은 top부터 bottom까지, 열은 left부터 right까지입니다. 한 바퀴를 돌 때는 맨 위 행을 left에서 right까지 읽고, 오른쪽 열을 top+1부터 bottom까지 내려가며 읽고, 맨 아래 행을 right-1에서 left까지 거꾸로 읽고, 왼쪽 열을 bottom-1에서 top+1까지 올라가며 읽습니다. 각 변은 앞선 변의 끝에서 한 칸 지난 곳부터 시작하므로 모든 모서리를 정확히 한 번씩 읽습니다. 그런 다음 네 경계를 모두 안쪽으로 한 칸씩 옮기고 top ≤ bottom이고 left ≤ right인 동안 반복합니다.

주의할 점은 한 행 또는 한 열 두께밖에 되지 않는 고리에서는 되돌아가는 경로가 이미 읽은 칸을 다시 지나간다는 것입니다. 두 번째 예시에서 바깥 고리를 돈 뒤의 경계는 top = bottom = 1, left = 1, right = 2입니다. 즉, 한 행 9, -4만 남습니다. 맨 위 행에서 두 값을 모두 읽고 나면 top 아래의 오른쪽 열에는 읽을 값이 없습니다. 하지만 맨 아래 행은 같은 행이므로, 그 행을 거꾸로 읽으면 9를 두 번째로 더하게 됩니다. 따라서 top < bottom이고 left < right인 경우에만 맨 아래 행과 왼쪽 열을 읽습니다. 세 번째 예시는 반대의 경우입니다. 한 열 4, 1, 7에서 왼쪽 열을 거꾸로 올라가며 읽으면 1을 다시 읽게 됩니다.

모든 값을 한 번씩 읽으므로 시간 복잡도는 O(m × n)입니다. 답에 모든 값이 들어가므로 이는 가능한 최소 시간입니다. 답을 제외한 메모리 사용량은 정수 네 개입니다.

알고리즘

top = 0, bottom = m-1, left = 0, right = n-1로 설정합니다.
top ≤ bottom이고 left ≤ right인 동안, left에서 right까지 맨 위 행을 읽고 top+1에서 bottom까지 맨 오른쪽 열을 읽습니다.
top < bottom이고 left < right이면, right-1에서 left까지 맨 아래 행을 읽고 bottom-1에서 top+1까지 맨 왼쪽 열을 읽습니다.
top과 left에 1을 더하고, bottom과 right에서 1을 뺍니다.
읽은 순서대로 값을 반환합니다.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

함정과 경계 사례

반복문은 짧으므로 버그는 모서리와 마지막 레이어에 있습니다.

마지막 레이어가 한 행 또는 한 열일 때 두 번 읽기. top < bottom 및 left < right 검사가 없으면 두 번째 예제의 결과는 9, -4, 9가 되고, 세 번째 예제에서는 4, 1, 7, 1을 읽습니다.
모서리를 두 번 읽기. 각 변을 각자의 첫 번째 셀부터 마지막 셀까지 읽으면 모든 모서리를 두 변이 읽게 됩니다. 각 변은 이전 변이 끝난 셀에서 한 셀 다음부터 시작하세요.
top ≤ bottom 대신 top < bottom인 동안 반복하기. 홀수 크기의 정사각형에서 가운데에 도달하기 전에 반복이 멈춥니다. 3 × 3 행렬에서는 가운데 값이 절대 읽히지 않습니다.
정사각형이 아닌 행렬에서 행과 열을 혼동하기. 두 경계에 모두 matrix.length를 사용하면 모든 정사각형 테스트에서는 작동하지만 3 × 4에서는 실패합니다.
얇은 입력을 빠뜨리기: 한 행, 한 열, 한 셀. 각각은 맨 아래 행이나 맨 왼쪽 열에 도달하지 않는 단일 레이어입니다.
R에서는 a:b에서 a > b이면 역순으로 세므로, 3:2와 같은 빈 범위는 아무것도 반환하는 대신 3, 2를 반환합니다. 가드 조건을 추가하거나 seq_len을 사용하세요. Lua와 R에서는 행과 열이 1부터 시작합니다.

자주 묻는 질문4

Spiral Matrix의 시간 및 공간 복잡도는 얼마인가요?

두 접근 방식 모두 각 값을 한 번씩 읽으므로 시간 복잡도는 O(m × n)이며, 답에 모든 값이 포함되기 때문에 이보다 더 나은 해결 방법은 없습니다. 네 개의 경계를 사용해 층을 벗겨 내는 방식은 답을 제외하면 O(1)의 추가 메모리를 사용합니다. 막히면 방향을 바꾸며 이동하는 방식은 읽은 셀을 기억하기 위해 O(m × n) 크기의 격자를 사용합니다.

나선형 순회에서 값을 두 번 읽지 않으려면 어떻게 해야 하나요?

두 곳에서 중복이 발생합니다. 모서리에서는 각 변을 이전 변이 끝난 셀의 다음 셀에서 시작하여 각 모서리가 한 변에만 포함되도록 합니다. 마지막 층에서는 행이 둘 이상이고 열도 둘 이상인 경우에만 아래쪽 행과 왼쪽 열을 읽습니다. 그렇지 않으면 되돌아가는 경로가 이미 읽은 셀을 지나가기 때문입니다.

행렬을 읽는 대신 나선형 순서로 채우려면 어떻게 해야 할까요?

같은 네 개의 경계와 같은 네 개의 변을 사용하되, 읽는 대신 씁니다. 1에서 시작하는 카운터를 유지하고, 각 셀을 지나갈 때마다 그 값을 저장하며 1씩 더합니다. n × n 행렬의 경우 카운터는 n²에서 끝나며, 위의 첫 번째 예시는 4 × 3 격자에 이렇게 적용한 결과입니다.

막혔을 때 오른쪽으로 돌면 왜 나선형이 만들어질까요?

첫 번째 순회에서 워커는 행렬의 네 모서리에서 방향을 바꿉니다. 이후 각 순회에서는 이전에 읽은 셀이 벽 역할을 하므로, 매번 직전 순회에서 걸었던 고리보다 한 셀 안쪽에서 방향을 바꿉니다. 이렇게 하면 각 순회가 이전 순회 안에 머물게 되며, 이것이 나선형입니다. 워커는 자신이 몇 번째 층에 있는지 알 필요가 없고, 다음 셀이 비어 있는지만 알면 됩니다.

Python

def spiralOrder(matrix):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]

기대값

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]