Transpose Matrix
정수 행렬을 행 목록으로 받습니다. matrix[i][j]는 i행 j열의 값입니다. 이 행렬의 전치 행렬을 반환하세요. 즉, i행 j열의 값은 j행 i열로 이동하므로 모든 행이 열이 됩니다. 행렬은 정사각형일 필요가 없습니다. m × n 행렬은 n × m 행렬이 됩니다.
함수
- matrixinteger-2d-array
- m개의 행과 각 행에 n개의 정수가 있는 m × n 행렬
- 반환값integer-2d-array
- n개의 행으로 이루어진 목록으로 나타낸 n × m 전치 행렬(각 행은 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]입니다. 즉, 3 × 2 행렬입니다.
- 입력
- matrix = [[1, 2], [3, 4]]
- 출력
- [[1, 3], [2, 4]]
- 설명
- 대각선 값 1과 4는 그대로 있습니다. 나머지 두 값은 자리를 바꿉니다. 2는 0행 1열에서 1행 0열로 이동하고, 3은 반대 방향으로 이동합니다.
후속 질문
행마다 이어서 저장된 m × n개의 값으로 이루어진 하나의 평탄한 배열에 행렬이 저장되어 있다고 가정해 봅시다. 두 번째 배열 없이 그 배열 안에서 직사각형 행렬을 전치할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
입력에
m개의 행과n개의 열이 있다면, 답에는 행과 열이 각각 몇 개 있나요?값이 변환 전과 후에 어디에 위치하는지 비교해 보세요.
i행j열의 값은j행i열에 위치하게 됩니다.각각
m개의 값을 가진n개의 행으로 결과를 만든 다음, 입력의 모든 셀을 반복하면서matrix[i][j]를result[j][i]에 복사합니다.
풀이
전치 연산은 아무것도 계산하지 않습니다. (i, j)의 값이 (j, i)로 이동합니다. 작업은 모양을 바꾸는 것입니다. 결과는 길이가 m인 행이 n개이므로, 행으로 이루어진 정사각형이 아닌 목록은 제자리에서 전치할 수 없습니다. 크기가 바뀐 새 행렬을 만들고 값을 채우세요.
행렬을 한 번에 한 열씩 읽으세요
핵심 아이디어
정답의 j번째 행은 입력의 j번째 열을 위에서 아래로 읽은 것입니다. [[1, 2, 3], [4, 5, 6]]에서 0번째 열은 1 다음에 4를 읽으므로 정답의 첫 번째 행은 [1, 4]입니다.
각 값은 한 번 읽고 한 번 씁니다. 시간은 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 격자를 채우기
핵심 아이디어
n × m 결과를 미리 만들고, 입력을 저장된 순서대로 행마다 읽은 다음 각 값을 서로 뒤바뀐 위치에 넣으세요: result[j][i] = matrix[i][j]. 전치란 모든 셀에 한 번씩 적용하는 바로 이 인덱스 교환이므로 올바릅니다.
각 값은 한 번씩 복사되므로 시간 복잡도는 O(m × n)이고, 격자는 어차피 출력에 필요한 O(m × n) 공간을 차지합니다. 행을 따라 읽으면 메모리에 저장된 순서대로 방문하며, 결과의 각 행은 최종 크기로 한 번만 할당됩니다.
알고리즘
m을 행의 개수,n을 한 행의 길이라고 하세요.n개의 행을 가진result를 만들고, 각 행에는m개의 값을 넣으세요.- 입력의 각 행
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
함정과 경계 사례
- 입력의 형태로 결과를 만드는 것. 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으로 읽습니다.
자주 묻는 질문3
행렬의 전치란 무엇인가요?
행과 열을 서로 바꾸어 얻는 행렬입니다. 행 i, 열 j에 있는 값은 행 j, 열 i로 이동합니다. 2 × 3 행렬은 3 × 2 행렬이 되며, 두 번 전치하면 원래 행렬로 돌아옵니다.
행렬을 전치하는 시간 복잡도는 얼마인가요?
O(m × n): m × n개의 값이 각각 한 번씩 복사되며, 이보다 적게 복사해서는 답을 만들 수 없습니다. 새 행렬은 출력 자체의 크기인 O(m × n)의 공간을 차지합니다.
행렬을 제자리에서 전치할 수 있나요?
정사각 행렬이라면 가능합니다. 대각선 위의 모든 셀에 대해 matrix[i][j]와 matrix[j][i]를 교환하면 되며, 추가 메모리는 O(1)입니다. 정사각형이 아닌 행렬은 형태가 바뀌므로, 행의 리스트를 사용한다면 새 행렬이 필요합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def transpose(matrix):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
matrix = [[1, 2, 3], [4, 5, 6]]
예상 출력
[[1, 4], [2, 5], [3, 6]]