[LeetCode] - 867. Transpose Matrix

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Transpose Matrix" 문제입니다.

--> https://leetcode.com/problems/transpose-matrix/description/

 

문제 : 

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices.

---

Example 1 :

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

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

 

Example 2 :

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

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

 

Constraints :

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 10^5
• -10^9 <= matrix[i][j] <= 10^9

---

주어진 문제는 2D 정수 배열 matrix의 전치 행렬(Transpose)을 반환하는 것입니다. 전치 행렬은 행렬을 주 대각선을 기준으로 뒤집어 행과 열의 인덱스를 교환한 것입니다. 예를 들어, 주어진 행렬의 전치 행렬을 구하면, 행과 열이 바뀐 새로운 행렬이 생성됩니다.

전치 행렬의 이해 

• 전치 행렬(Transpose) : 선형대수를 배우셨으면 아시겠지만, 혹여나 잘 모르시거나, 기억이 잘 안나시는 분들을 위해서 설명드리겠습니다 : 
  • 주어진 행렬에서 행과 열을 교환하여 새로운 행렬을 만듭니다.
  • 예를 들어, 원래 행렬의 (i, j) 요소가 전치 행렬에서는 (j, i) 위치에 놓입니다.
  • 결과적으로, 원래 행렬의 행(row)은 전치 행렬의 열(column)이 되고, 원래 행렬의 열(column)은 전치 행렬의 행(row)이 됩니다.

class Solution {
    public int[][] transpose(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] transpose = new int[cols][rows];
        
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                transpose[c][r] = matrix[r][c];
            }
        }

        return transpose;
    }
}

 

이번 문제는 선형대수를 통해서 전치 행렬의 개념을 잘 아시는 분이라면 쉽게 풀 수 있었던 문제라고 판단됩니다. 초보분들께도 행렬의 개념을 더 학습할 수 있는 좋은 기회라고 생각되기에 추천드립니다. 

1. 행렬 크기 파악 :
   • rows는 원래 행렬의 행(row) 수를 나타냅니다.
   • cols는 원래 행렬의 열(column) 수를 나타냅니다.
2. 전치 행렬 초기화 :
   • 전치 행렬의 크기는 원래 행렬의 행과 열을 바꾼 것입니다. 따라서 cols x rows 크기로 새로운 2D 배열 transpose를 초기화합니다.
3. 요소 복사 및 위치 변경 :
   • 이중 루프를 통해 원래 행렬의 모든 요소를 순회합니다.
     • 외부 루프는 열 c를 순회합니다.
     • 내부 루프는 행 r를 순회합니다.
   • transpose[c][r] = matrix[r][c];는 원래 행렬의 r행, c열의 요소를 전치 행렬의 c행, r열에 저장합니다. 이는 행과 열을 교환하여 전치 행렬을 만드는 핵심 로직입니다.
4. 끝

시간 복잡도

• O(m * n) : 여기서 m은 원래 행렬의 행(row) 수이고 n은 열(column) 수입니다. 코드가 행렬의 모든 요소를 한 번씩 접근하여 복사하므로 시간 복잡도는 O(m * n)입니다.

공간 복잡도

• O(n * m) : 새로운 전치 행렬을 저장하기 위한 추가적인 공간이 필요합니다. 전치 행렬의 크기는 n x m이므로, 공간 복잡도는 O(n * m)입니다.

---

코드 Runtime 결