C++로 행렬의 수정된 평균보다 큰 요소 개수 구하기

행렬의 수정된 평균이란?

행렬의 수정된 평균(modified mean)은 일반적인 산술 평균과 달리, 다음 공식으로 정의됩니다.

(각 행 최솟값의 합 + 각 열 최댓값의 합) ÷ (행의 개수 + 열의 개수)

예를 들어 다음과 같은 3×3 행렬이 있다고 가정해 보겠습니다.

1 2 3
4 5 6
7 8 9

이 행렬의 수정된 평균은 아래와 같이 계산할 수 있습니다.

mean = (sum(1 + 4 + 7) + sum(7 + 8 + 9)) / (3 + 3)
     = (12 + 24) / 6
     = 6

즉, 먼저 수정된 평균을 구한 뒤, 그 평균보다 큰 요소의 개수를 세면 됩니다. 위 예제에서 평균은 6이며, 6보다 큰 요소는 7, 8, 9로 총 3개입니다.

알고리즘

문제를 해결하는 절차는 다음과 같습니다.

1. 행렬을 초기화합니다.
2. 각 행의 최솟값을 찾아 그 합(rowSum)을 구합니다.
3. 각 열의 최댓값을 찾아 그 합(colSum)을 구합니다.
4. 앞서 소개한 공식으로 수정된 평균을 계산합니다.
5. 행렬 전체를 순회하면서 평균보다 큰 요소의 개수를 셉니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define m 3
#define n 3
int getElementCountGreaterThanMean(int matrix[][n]) {
    int rowSum = 0;
    // 각 행의 최솟값을 찾아 합산
    for (int i = 0; i < m; i++) {
        int min = matrix[i][0];
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] < min) {
                min = matrix[i][j];
            }
        }
        rowSum += min;
    }
    int colSum = 0;
    // 각 열의 최댓값을 찾아 합산
    for (int i = 0; i < n; i++) {
        int max = matrix[0][i];
        for (int j = 1; j < m; j++) {
            if (max < matrix[j][i]) {
                max = matrix[j][i];
            }
        }
        colSum += max;
    }
    // 수정된 평균 계산
    int mean = (rowSum + colSum) / (m + n);
    // 평균보다 큰 요소 개수 카운트
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mean < matrix[i][j]) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int matrix[m][n] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    cout << getElementCountGreaterThanMean(matrix) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

3

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(m × n)입니다. 행별 최솟값 탐색, 열별 최댓값 탐색, 마지막 요소 개수 카운트 모두 행렬의 모든 원소를 한 번씩만 확인하기 때문입니다. 공간 복잡도는 추가 배열 없이 상수 변수만 사용하므로 O(1)입니다.