[LeetCode] 566. Reshape the Matrix

문제 출처: https://leetcode.com/problems/reshape-the-matrix/

Reshape the Matrix - LeetCode

 

문제

MATLAB에는, m x n 행렬을 데이터는 유지한 채 r x c의 다른 형태의 행렬로 재구성하는 reshape 함수가 존재한다.

 

m x n 행렬 mat이 주어지고, 재구성 후의 행과 열의 크기를 의미하는 두 정수 r과 c가 주어진다.

재구성된 행렬은 이전 행렬과 완전히 동일한 원소로 이전과 동일한 행 순회 순서로 채워져야 한다.

 

만약 주어진 파라미터로 reshape이 가능하다면, 재구성된 행렬을 반환하고, 아니라면 원래의 행렬을 반환하라.

예제

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

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

풀이

2차원의 행렬을 1차원으로 변경하는 것은 2중 반복문을 이용해서 어렵지 않게 수행할 수 있을 것이다.

 

그렇다면 반대로 1차원의 행렬을 2차원으로 변경하는 것은 어떠한가. 단순한 예를 하나 생각해보자.

origin matrix = [1, 2, 3, 4, 5, 6], r = 3, c = 2

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

origin_index        reshaped_index
0                    (0, 0)
1                    (0, 1)
2                    (1, 0)
3                    (1, 1)
4                    (2, 0)
5                    (2, 1)

위의 인덱스 변환 내용을 통해서 아래와 같은 수식을 도출할 수 있다.

• reshaped_index's row = origin_index / c
• reshaped_index's column = origin_index % c

 

마지막으로 2차원에서 2차원으로의 변환은 어떻게 할 수 있을까. 단순하게 2차원 -> 1차원 -> 2차원으로 변형하는 과정을 통해서 해결할 수 있다.

 

이 과정을 코드로 작성하면 다음과 같다.

var matrixReshape(mat, r, c) {
    // 주어진 행렬을 1차원으로 변경
    const oneDim = mat.flat();

    // 1차원 행렬을 2차원으로 변경
    const reshaped = Array(r).fill(0).map(val => []);
    for (let i = 0; i < oneDim.length; i++) {
        reshaped[i / c].push(oneDim[i]);
    }

    return reshaped;
}

위 코드에서 1차원을 2차원으로 바꾸는 부분을 자세히 보면, 이전에 언급했던 reshaped_index's column = origin_index % c을 사용하지 않고 행 위치만 계산하여 배열에 추가하는 것을 볼 수 있다.

 

최종적으로 주어진 파라미터로 reshape이 가능한지 안한지에 대한 판단만 해주면 되는데, 이는 원래 행렬의 원소 수가 변경하고자 하는 사이즈의 행렬의 원소 수와 같은지 체크하는 것으로 구할 수 있다.

var matrixReshape(mat, r, c) {
    if ((r*c) != (mat.length * mat[0].length)) { return mat; }

    // 주어진 행렬을 1차원으로 변경
    const oneDim = mat.flat();

    // 1차원 행렬을 2차원으로 변경
    const reshaped = Array(r).fill(0).map(val => []);
    for (let i = 0; i < oneDim.length; i++) {
        reshaped[i / c].push(oneDim[i]);
    }

    return reshaped;
}

 

Github: 566.js

opwe37/Algorithm-Study