C++로 행렬 형태 변환(Reshape) 구현하기

다양한 프로그래밍 플랫폼에는 reshape라는 매우 유용한 함수가 존재합니다. 이 함수는 행렬의 데이터는 그대로 유지한 채, 크기만 다른 새로운 행렬로 변환해 주는 역할을 합니다.

예를 들어, 하나의 행렬과 원하는 재구성 행렬의 행 개수 r, 열 개수 c가 주어졌다고 가정해 보겠습니다. 입력이 [[5,10],[15,20]]이고 row = 1, col = 4라면, 출력은 다음과 같습니다.

[[5, 10, 15, 20]]

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 1차원 임시 배열 temp를 정의합니다.
• 크기가 r × c인 2차원 배열 res를 생성합니다.
• 카운터 변수 count를 0으로 초기화합니다.
• 원본 행렬 nums의 모든 요소를 순회하며 temp에 순서대로 삽입합니다.
• 만약 r * c가 원본 행렬의 전체 요소 개수와 일치하지 않으면, 변환이 불가능하므로 원본 행렬 nums를 그대로 반환합니다.
• 그렇지 않다면, temp의 요소들을 차례대로 꺼내어 res[i][j]에 채워 넣고 최종 결과를 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}

class Solution {
public:
   vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
      vector<int> temp;
      vector<vector<int> > res(r, vector<int>(c));
      int count = 0;
      for (int i = 0; i < nums.size(); i++) {
         for (int j = 0; j < nums[0].size(); j++) {
            temp.push_back(nums[i][j]);
         }
      }
      if (r * c != nums.size() * nums[0].size())
         return nums;
      for (int i = 0; i < r; i++) {
         for (int j = 0; j < c; j++) {
            res[i][j] = temp[count++];
         }
      }
      return res;
   }
};

main(){
   Solution ob;
   vector<vector<int>> v = {{5,10},{15,20}};
   print_vector(ob.matrixReshape(v, 1, 4));
}

입력

{{5,10},{15,20}}, 1, 4

출력

[[5, 10, 15, 20]]

코드 설명 및 시간 복잡도

위 알고리즘의 동작 과정을 정리하면 다음과 같습니다.

• 1단계: 2차원 행렬의 모든 값을 1차원 벡터 temp에 펼쳐 담습니다.
• 2단계: 목표 크기(r × c)와 원본 행렬의 전체 요소 수가 다르면 재구성이 불가능하므로 원본을 그대로 반환합니다.
• 3단계: temp에 저장된 값들을 왼쪽에서 오른쪽으로, 위에서 아래로 순서대로 새 행렬 res에 배치합니다.

이 방식의 시간 복잡도는 행렬의 전체 요소 개수에 비례하여 O(m × n)이며, 공간 복잡도 역시 결과 행렬을 저장하기 위해 O(m × n)입니다. 여기서 m과 n은 각각 원본 행렬의 행과 열의 개수를 의미합니다.