[LeetCode] 566. Reshape the Matrix - 문제풀이

Description

주어진 2차원 배열(행렬)을 rxc의 행렬로 재구성하는 문제입니다.

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

Example 2:

Input: mat = [[1,2],[3,4]], r = 2, c = 4
Output: [[1,2],[3,4]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• -1000 <= mat[i][j] <= 1000
• 1 <= r, c <= 300

Solution 1. Row,Column index 재계산 

public int[][] matrixReshape(int[][] mat, int r, int c) {

    int m = mat.length;
    int n = mat[0].length;
    if(m <= r && n <= c ){ return mat; } // Reshape 필요 없는 케이스
    if(m*n != r*c){ return mat; } // Reshape 불가

    //convert to new Matrix
    int[][] newMat = new int[r][c];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int idx = (i*n)+j; // 1차원일때 인덱스
            int nr = idx / c;  // row index 12/6 = 2
            int nc = idx % c;  // column index 12/6 = 0
            newMat[nr][nc] = mat[i][j];
        }
    }
    return newMat;
}

새로운 크기인 r x c 로 재구성이 불가능한 엣지 케이스들은 제외 해 준뒤 기존 행렬(mat)의 요소를 행,렬 순서대로 반복하며 새로운 사이즈의 행렬(newMat)에 순서대로 채워줍니다. 새로운 인덱스는 nr,nc는 현재 요소의 1차원 일때의 인덱스에서 컬럼수로 나눈 것이 새로운 row의 인덱스가 되고 컬럼수로 나눈 나머지가 새로운 column의 인덱스가 됩니다.

• 시간 복잡도 : O(M+N)
• 시간 복잡도 : O(M+N)

Reference

Reshape the Matrix - LeetCode