Transpose Matrix

Q: 행렬의 전치란 무엇인가요?

행과 열을 서로 바꾸어 얻는 행렬입니다. 행 i , 열 j 의 값은 행 j , 열 i 로 이동합니다. 2 × 3 행렬은 3 × 2 행렬이 되며, 두 번 전치하면 원래 행렬로 돌아옵니다.

Q: 행렬을 전치하는 시간 복잡도는 얼마인가요?

각 m × n 값이 한 번씩 복사되고, 이보다 적은 작업으로는 답을 만들 수 없으므로 O(m × n) 입니다. 새 행렬은 O(m × n) 의 공간을 차지하며, 이는 출력 자체의 크기입니다.

Q: 행렬을 제자리에서 전치할 수 있나요?

정사각 행렬이라면 가능합니다. 추가 메모리 O(1) 을 사용해 대각선 위의 모든 셀에서 matrix[i][j] 와 matrix[j][i] 를 서로 바꾸면 됩니다. 정사각형이 아닌 행렬은 결과의 모양이 달라지므로, 행 목록으로 표현된 경우 새 행렬이 필요합니다.

Q: 정사각형이 아닌 행렬은 어떻게 전치하나요?

입력의 행이 m 개이고 각 행의 길이가 n 일 때, 행이 n 개이고 각 행의 길이가 m 인 결과를 만드세요. 그런 다음 result[j][i] = matrix[i][j] 를 사용해 모든 값을 복사하세요. 두 행렬의 모양이 같지 않으므로 정사각형의 대각선 개념은 적용되지 않습니다.

입문배열과 문자열

+10

정수 행렬을 행의 리스트로 받습니다. matrix[i][j]는 i행 j열의 값입니다. 행을 열로 바꾼 행렬인 전치 행렬을 반환하세요. i행 j열의 값은 j행 i열로 이동합니다. 행렬은 정사각형일 필요가 없습니다. m × n 행렬은 n × m 행렬이 됩니다.

함수

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

matrixinteger-2d-array: m개의 행과 각 행에 n개의 정수가 있는 m × n 행렬
반환값integer-2d-array: n개의 행으로 이루어지고 각 행에 m개의 정수가 있는 리스트 형태의 n × m 전치 행렬

제약 조건

1 ≤ m, n ≤ 1000, 여기서 m = matrix.length이고 n = matrix[i].length입니다.
m × n ≤ 5000
모든 행의 길이는 n으로 같습니다.
-1000 ≤ matrix[i][j] ≤ 1000

예제

입력: matrix = [[1, 2, 3], [4, 5, 6]]
출력: [[1, 4], [2, 5], [3, 6]]
설명: 첫 번째 행 [1, 2, 3]은 첫 번째 열이 되고 [4, 5, 6]은 두 번째 열이 됩니다. 결과를 행별로 읽으면 [1, 4], [2, 5], [3, 6]이 됩니다. 2 × 3 행렬이 3 × 2 행렬로 바뀌었습니다.

제출 시 숨은 테스트 +15개

후속 질문

행렬이 m × n개의 값으로 이루어진 하나의 평평한 배열에 행별로 저장되어 있다고 가정해 보세요. 두 번째 배열 없이 그 배열 안에서 정사각형이 아닌 행렬을 전치할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

전치는 주소만 순수하게 바꾸는 작업입니다. (i, j)의 값이 (j, i)로 이동하며, 계산되는 것은 없습니다. 올바른 형태를 갖추는 것이 핵심입니다. 행의 리스트로 저장된 정사각형이 아닌 행렬은 제자리에서 전치할 수 없습니다. 결과는 길이가 m인 행 n개가 아니라 길이가 n인 행 m개를 가지므로, 크기를 서로 바꾼 새 행렬을 만들고 값을 채워야 합니다.

행렬을 한 열씩 읽으세요

핵심 아이디어

답의 j번째 행은 입력의 j번째 열을 위에서 아래로 읽은 것입니다. 따라서 답을 한 번에 한 행씩 만드세요. 0부터 n-1까지 각 열 j에 대해 matrix[0][j], matrix[1][j] 등을 matrix[m-1][j]까지 모은 다음, 그 목록을 다음 행으로 추가하세요.

[[1, 2, 3], [4, 5, 6]]의 경우, 0번째 열은 1 다음에 4, 1번째 열은 2 다음에 5, 2번째 열은 3 다음에 6을 읽습니다. 답은 [[1, 4], [2, 5], [3, 6]]이며, m = 2개의 값이 있는 행이 n = 3개입니다.

각 값은 한 번 읽고 한 번 쓰므로 시간 복잡도는 O(m × n)이고, 결과에 O(m × n)의 공간이 필요합니다. 비용은 접근 패턴에서 발생합니다. 새 행 하나를 만들 때 입력의 모든 행을 건드리며, 한 행을 따라 읽는 대신 행에서 행으로 건너뜁니다.

알고리즘

m을 행의 개수로, n을 한 행의 길이로 둡니다.
0부터 n-1까지 각 열 j에 대해 빈 리스트를 시작합니다.
0부터 m-1까지 모든 i에 대해 matrix[i][j]를 그 리스트에 추가합니다.
그 리스트를 j번째 행으로 결과에 추가하고, 마지막 열을 처리한 후 결과를 반환합니다.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

각 셀을 대칭시켜 새로운 n × m 격자를 채우세요

핵심 아이디어

먼저 모양을 정한 다음 채우세요. 정답은 길이가 m인 행 n개로 이루어지므로, 먼저 그리드를 만드세요. 그런 다음 입력을 자연스러운 순서대로, 행별로 왼쪽에서 오른쪽으로 읽고 각 값을 뒤바뀐 위치에 넣으세요: result[j][i] = matrix[i][j].

전치란 두 인덱스를 서로 바꾸는 것이므로 이 규칙은 올바릅니다. 정사각형 예시 [[1, 2], [3, 4]]에서 대각선 위의 1과 4는 원래 위치에 그대로 있고, 2는 (0, 1)에서 (1, 0)으로, 3은 (1, 0)에서 (0, 1)로 이동하여 [[1, 3], [2, 4]]가 됩니다.

m × n개의 값을 각각 한 번씩 복사하므로 시간 복잡도는 O(m × n)이고, 새 그리드는 어차피 출력에 필요한 O(m × n)의 공간을 사용합니다. 입력을 행을 따라 읽으면 메모리에 저장된 순서대로 방문하게 되며, 결과의 각 행은 최종 크기로 한 번만 만들어집니다.

알고리즘

m을 행의 개수로, n을 한 행의 길이로 둡니다.
n개의 행을 갖고 각 행에 m개의 값이 들어 있는 result를 만듭니다.
입력의 각 행 i와 각 열 j에 대해 result[j][i] = matrix[i][j]로 설정합니다.
result를 반환합니다.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

함정과 경계 사례

잘못된 답변의 거의 대부분은 값이 아니라 모양에서 비롯됩니다.

원본과 같은 모양으로 결과를 만드는 경우. m개의 행과 n개의 열로 된 결과는 정사각형 입력에서만 작동합니다. 2 × 3 예제에서 result[2][0]을 쓰면 범위를 벗어납니다. 결과에는 길이가 m인 행이 n개 있어야 합니다.
정사각형이 아닌 행렬에서 제자리 교환을 하는 경우. matrix[i][j]와 matrix[j][i]를 교환하는 방법은 m = n일 때만 작동합니다. 이 경우에도 반복문은 대각선 위의 셀만 포함해야 합니다(j > i). 그렇지 않으면 각 쌍을 두 번 교환하여 행렬이 원래 상태로 돌아옵니다.
하나의 행 객체를 공유하는 경우. Python에서 [[0] * m] * n은 같은 리스트를 n번 참조하므로, 한 셀에 값을 쓰면 열 전체에 값이 써집니다. 각 행을 따로 만드세요.
C에서 열 크기를 잊는 경우. 호출하는 쪽은 *returnSize를 결과 행의 개수인 n으로 읽고, (*returnColumnSizes)[j]를 각 행의 길이인 m으로 읽습니다.

자주 묻는 질문4

행렬의 전치란 무엇인가요?

행과 열을 서로 바꾸어 얻는 행렬입니다. 행 i, 열 j의 값은 행 j, 열 i로 이동합니다. 2 × 3 행렬은 3 × 2 행렬이 되며, 두 번 전치하면 원래 행렬로 돌아옵니다.

행렬을 전치하는 시간 복잡도는 얼마인가요?

각 m × n 값이 한 번씩 복사되고, 이보다 적은 작업으로는 답을 만들 수 없으므로 O(m × n)입니다. 새 행렬은 O(m × n)의 공간을 차지하며, 이는 출력 자체의 크기입니다.

행렬을 제자리에서 전치할 수 있나요?

정사각 행렬이라면 가능합니다. 추가 메모리 O(1)을 사용해 대각선 위의 모든 셀에서 matrix[i][j]와 matrix[j][i]를 서로 바꾸면 됩니다. 정사각형이 아닌 행렬은 결과의 모양이 달라지므로, 행 목록으로 표현된 경우 새 행렬이 필요합니다.

정사각형이 아닌 행렬은 어떻게 전치하나요?

입력의 행이 m개이고 각 행의 길이가 n일 때, 행이 n개이고 각 행의 길이가 m인 결과를 만드세요. 그런 다음 result[j][i] = matrix[i][j]를 사용해 모든 값을 복사하세요. 두 행렬의 모양이 같지 않으므로 정사각형의 대각선 개념은 적용되지 않습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

입력

matrix = [[1, 2, 3], [4, 5, 6]]

기대값

[[1, 4], [2, 5], [3, 6]]