C++로 구현하는 행렬 0의 개수 기준 열 인덱스 정렬 프로그램

문제 개요

N개의 행과 M개의 열로 이루어진 NxM 크기의 행렬이 주어졌을 때, 각 열에 포함된 0의 개수를 기준으로 열들을 정렬한 뒤, 정렬된 순서대로 해당 열의 인덱스를 출력하는 것이 이번 문제의 목표입니다.

예를 들어 첫 번째 열에 0이 1개 있고, 두 번째 열에는 0이 하나도 없으며, 세 번째 열에 0이 2개 있다고 가정해 보겠습니다. 이 경우 0이 적은 열부터 오름차순으로 정렬하면 결과는 2 1 3이 됩니다.

예시

설명: 위 행렬에서 1번째 열의 0은 1개(0, 1, 1), 2번째 열의 0은 2개(0, 1, 0), 3번째 열의 0은 1개(0, 1, 1)입니다. 0의 개수를 기준으로 오름차순 정렬하면 1번 열(1개) → 3번 열(1개) → 2번 열(2개) 순서가 되므로 최종 결과는 1 3 2입니다.

참고: 행렬의 인덱스는 1부터 시작하는 것으로 간주합니다.

접근 방법

각 열을 순회하면서 해당 열에 포함된 0의 개수를 계산합니다.
(0의 개수, 열 인덱스) 형태의 쌍(pair)을 벡터에 저장합니다.
벡터를 오름차순으로 정렬합니다. C++의 pair 정렬 특성상 0의 개수가 같으면 열 인덱스가 작은 순서대로 정렬됩니다.
정렬된 벡터를 순회하며 열 인덱스에 1을 더해 출력합니다.

C++ 구현 코드

#include <bits/stdc++.h>
#define row 3
#define col 3
using namespace std;
void sorting(int arr[row][col]){
    vector<pair<int, int> > count_zero;
    for (int i = 0; i < col; i++){
        int count = 0;
        for (int j = 0; j < row; j++){
            if (arr[j][i] == 0)
                count++;
        }
        count_zero.push_back(make_pair(count, i));
    }
    sort(count_zero.begin(), count_zero.end());
    for (int i = 0; i < col; i++)
        cout << count_zero[i].second + 1 << " ";
}
int main(){
    int array[row][col] = {
        { 0, 0, 0 },
        { 1, 1, 1 },
        { 1, 0, 1 }
    };
    cout << "sorted order of zeroes count is : ";
    sorting(array);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

sorted order of zeroes count is : 1 3 2

코드 설명 및 시간 복잡도

sorting() 함수는 바깥쪽 반복문으로 각 열을 순회하고, 안쪽 반복문으로 해당 열의 각 행을 검사하여 0의 개수를 셉니다. 이후 (count, i) 쌍을 벡터에 저장한 뒤 STL의 sort() 함수로 정렬합니다. 정렬이 완료되면 각 쌍의 두 번째 값(열 인덱스)에 1을 더해 출력함으로써 1부터 시작하는 열 번호를 얻을 수 있습니다.

모든 행렬 요소를 확인하여 0의 개수를 세는 데 O(N×M)의 시간이 소요되고, M개의 쌍을 정렬하는 데 O(M log M)의 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(N×M + M log M)입니다.