C++로 행렬을 대각선 방향으로 정렬하는 방법

N × M 크기의 행렬이 주어졌을 때, 각 대각선 요소들을 왼쪽 위에서 오른쪽 아래 방향으로 오름차순 정렬해야 하는 문제를 생각해 봅시다. 예를 들어 다음과 같은 행렬이 있다고 가정합니다.

대각선 기준으로 정렬한 후의 결과 행렬은 다음과 같습니다.

문제 해결 접근 방법

이 문제는 각 대각선을 하나의 그룹으로 묶어 정렬한 뒤, 원래 위치에 다시 배치하는 방식으로 해결할 수 있습니다. 핵심 아이디어는 같은 대각선에 속하는 좌표 (i, j)는 항상 i - j 값이 동일하다는 점입니다. 알고리즘 단계는 다음과 같습니다.

• 시작 좌표 si, sj와 행렬 mat을 인자로 받는 solve() 메서드를 정의합니다.

• n은 행의 개수, m은 열의 개수로 설정합니다.

• 대각선 요소를 임시로 저장할 배열 temp를 생성합니다.

• i := si, j := sj, index := 0으로 초기화합니다.

• i < n 이고 j < m 인 동안 반복하며 temp에 m[i, j] 값을 삽입하고, i와 j를 각각 1씩 증가시킵니다.

• temp 배열을 오름차순으로 정렬합니다.

• index := 0, i := si, j := sj로 다시 초기화합니다.

• i < n 이고 j < m 인 동안 mat[i, j] := temp[index]로 값을 되돌려 쓰고, i, j, index를 각각 1씩 증가시킵니다.

• 메인 메서드에서는 다음을 수행합니다.

• n := 행의 개수, m := 열의 개수로 설정합니다.

• i를 0부터 n-1까지 순회하며 solve(i, 0, mat)를 호출합니다. (첫 번째 열에서 시작하는 대각선)

• j를 1부터 m-1까지 순회하며 solve(0, j, mat)를 호출합니다. (첫 번째 행에서 시작하는 대각선)

• 정렬된 행렬 mat을 반환합니다.

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:
    void solve(int si, int sj, vector < vector <int> > &mat){
        int n = mat.size();
        int m = mat[0].size();
        vector <int> temp;
        int i = si;
        int j = sj;
        int idx = 0;
        while(i < n && j < m){
            temp.push_back(mat[i][j]);
            i++;
            j++;
        }
        sort(temp.begin(), temp.end());
        idx = 0;
        i = si;
        j = sj;
        while(i < n && j < m){
            mat[i][j] = temp[idx];
            i++;
            j++;
            idx++;
        }
    }
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        for(int i = 0; i <n; i++){
            solve(i, 0, mat);
        }
        for(int j = 1; j < m; j++){
            solve(0, j, mat);
        }
        return mat;
    }
};
main(){
    vector<vector<int>> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
    Solution ob;
    print_vector(ob.diagonalSort(v));
}

입력

[[3,3,1,1],[2,2,1,2],[1,1,1,2]]

출력

[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

복잡도 분석

이 알고리즘의 시간 복잡도는 O((N + M) × D log D)입니다. 여기서 D는 가장 긴 대각선의 길이(min(N, M))를 의미합니다. 각 대각선마다 요소를 추출하고 정렬한 뒤 다시 배치하기 때문입니다. 공간 복잡도는 임시 배열 temp를 사용하므로 O(min(N, M))입니다.