Rotate Image

Q: 행렬 회전의 시간 복잡도와 공간 복잡도는 무엇인가요?

n × n 행렬을 회전하는 데는 거의 모든 값이 한 번씩 이동해야 하므로 O(n²)의 시간이 걸립니다. 전치 후 뒤집는 방법은 O(1)의 추가 공간이 필요합니다. 회전된 복사본을 만드는 데도 O(n²)의 시간이 걸리지만 O(n²)의 추가 공간을 사용합니다.

Q: 한 번에 네 개의 값을 이동하여 행렬을 회전할 수 있나요?

네. 중앙에 있지 않은 모든 값은 네 개의 셀로 이루어진 순환에 속합니다. (i, j) , (j, n-1-i) , (n-1-i, n-1-j) 및 (n-1-j, i) 가 그 셀입니다. 고리마다 각 순환에서 값 하나를 변수에 보관하고 나머지 세 값을 이동합니다. 시간 복잡도는 O(n²), 공간 복잡도는 O(1)로 동일하지만, 잘못 입력할 수 있는 인덱스 계산이 더 많습니다.

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

+10

각 행마다 하나의 리스트가 있는 정수 n × n 격자를 받습니다. 이 격자를 시계 방향으로 90도 회전한 후 반환하세요. 맨 위 행은 가장 오른쪽 열이 되고, 두 번째 행은 그 왼쪽 열이 되는 식입니다. 즉, (i, j)에 있는 값은 (j, n-1-i)로 이동합니다. 격자를 제자리에서 변경해도 됩니다. 변경한 격자를 반환하세요.

함수

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

matrixinteger-2d-array: 정사각형 격자, 각 행마다 하나의 내부 목록
반환값integer-2d-array: 행렬이 시계 방향으로 90도 회전했습니다

제약 조건

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

예제

입력: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
출력: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
설명: 첫 번째 행인 3 7 1은 위에서 아래로 읽었을 때 마지막 열이 됩니다. 첫 번째 열인 3 9 4를 아래에서 위로 읽으면 첫 번째 행 [4, 9, 3]이 됩니다. 가운데 값 5는 그대로 있습니다.

후속 질문

행렬을 제자리에서 180도 회전시키는 두 단계는 무엇이며, 한 번의 교환 과정으로 할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

각 값이 어디로 이동하는지는 다음 공식으로 나타낼 수 있습니다: (i, j)는 (j, n-1-i)로 이동합니다. 어려운 점은 두 번째 행렬 없이 값을 옮기는 것입니다. 값을 새 셀에 쓰면 아직 이동하지 않은 값이 덮어써지기 때문입니다. 전치한 다음 행을 뒤집으면 쌍을 교환하여 같은 90도 회전을 만들 수 있습니다.

회전된 복사본 만들기

핵심 아이디어

행 i는 열 n-1-i가 되고, 행에서 위치 j에 있는 값은 해당 열에서 아래로 j번째 위치, 즉 행 j로 이동합니다. 따라서 result[j][n-1-i] = matrix[i][j]입니다. 첫 번째 예시에서는 행 2, 열 0에 있는 4가 행 0, 열 0으로 이동하므로 답이 4로 시작합니다.

값은 네 개씩 순환하며 이동하므로 제자리에서 쓰면 값이 이동하기 전에 다른 값으로 덮어쓰게 됩니다. 3이 오른쪽 위 모서리의 1을 덮어쓰게 되는 것이죠. 복사본에는 n = 70일 때 4,900개인 n²개의 추가 셀이 필요합니다.

알고리즘

n × n 결과 행렬을 만듭니다.
모든 행 i와 열 j에 대해 matrix[i][j]를 result[j][n-1-i]에 복사합니다.
결과를 반환합니다.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

전치한 다음 각 행을 뒤집으세요

핵심 아이디어

전치는 (i, j)를 (j, i)로 옮기고, 행을 뒤집으면 열 c가 열 n-1-c로 옮겨집니다. 두 연산을 함께 적용하면 (i, j)가 (j, n-1-i)로 옮겨지는데, 이는 회전했을 때 정확히 이동하는 위치입니다.

두 연산 모두 쌍을 이루는 원소를 서로 바꾸므로 제자리에서 수행됩니다. 전치할 때 matrix[i][j]와 matrix[j][i]는 서로의 위치로 가야 하므로 한 번만 서로 바꾸면 됩니다. j > i인 쌍만 바꾸세요. 그렇지 않으면 모든 쌍이 다시 원래대로 바뀝니다. 행을 뒤집을 때는 양 끝의 원소를 서로 바꾸면서 가운데로 이동합니다.

첫 번째 예시에서 전치하면 [[3, 9, 4], [7, 5, 8], [1, 2, 6]]이 됩니다. 이제 각 행에 이전의 열이 들어 있습니다. 각 행을 뒤집으면 답을 얻습니다.

전치에서는 n(n-1)/2번 원소를 서로 바꾸고, 행을 뒤집는 데는 n·⌊n/2⌋번 원소를 서로 바꾸므로, 변수 몇 개만 추가 메모리로 사용하면서 작업량은 O(n²)입니다. R 버전은 먼저 입력을 R 행렬로 복사하므로 추가 메모리는 O(n²)입니다.

알고리즘

주대각선 위의 모든 셀 (i, j)에서 j > i일 때, 해당 셀의 값을 셀 (j, i)의 값과 교환합니다.
각 행에서 첫 번째 값과 마지막 값을 바꾸고, 양쪽 끝이 만날 때까지 안쪽으로 이동합니다.
행렬을 반환합니다.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

함정과 경계 사례

j가 0에서 시작하도록 전치하기. 각 쌍이 두 번 교환되어 전치가 상쇄되므로, 결과는 행만 뒤집힌 거울상입니다.
전치하기 전에 뒤집기. 이 순서는 행렬을 반시계 방향으로 회전시킵니다. 2 × 2 테스트로 확인할 수 있습니다. [[1, 2], [3, 4]]는 [[3, 1], [4, 2]]가 되어야 합니다.
같은 행렬에 matrix[j][n-1-i] = matrix[i][j]를 쓰기. 대상 셀에는 아직 이동하지 않은 값이 들어 있으므로, 이 값이 손실됩니다.
n-1-i 대신 n-i 사용하기. 0부터 시작하는 인덱스에서는 마지막 열이 n-1이므로, i = 0일 때 n-i는 범위를 벗어납니다.

자주 묻는 질문3

행렬 회전의 시간 복잡도와 공간 복잡도는 무엇인가요?

n × n 행렬을 회전하는 데는 거의 모든 값이 한 번씩 이동해야 하므로 O(n²)의 시간이 걸립니다. 전치 후 뒤집는 방법은 O(1)의 추가 공간이 필요합니다. 회전된 복사본을 만드는 데도 O(n²)의 시간이 걸리지만 O(n²)의 추가 공간을 사용합니다.

행렬을 시계 반대 방향으로 어떻게 회전하나요?

두 단계의 순서를 바꾸세요. 먼저 각 행을 뒤집은 다음 전치합니다. 전치한 다음 행의 순서를 뒤집어도 됩니다. 어느 쪽이든 (i, j)의 값은 (n-1-j, i)에 위치하게 됩니다.

한 번에 네 개의 값을 이동하여 행렬을 회전할 수 있나요?

네. 중앙에 있지 않은 모든 값은 네 개의 셀로 이루어진 순환에 속합니다. (i, j), (j, n-1-i), (n-1-i, n-1-j) 및 (n-1-j, i)가 그 셀입니다. 고리마다 각 순환에서 값 하나를 변수에 보관하고 나머지 세 값을 이동합니다. 시간 복잡도는 O(n²), 공간 복잡도는 O(1)로 동일하지만, 잘못 입력할 수 있는 인덱스 계산이 더 많습니다.

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

테스트 #1

테스트 #2

인자

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

예상 출력

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