C++로 2차원 배열의 위치 요소(Positional Element) 개수 구하기

이 문제에서는 2차원 배열 mat[n][m]이 주어지며, 주어진 배열에서 위치 요소(positional element)의 개수를 구하는 것이 목표입니다.

여기서 위치 요소란, 해당 값이 자신이 속한 행(row) 또는 열(column)에서 최댓값 또는 최솟값에 해당하는 요소를 의미합니다.

예제 입력

mat[][] = {2, 5, 7}
{1, 3, 4}
{5, 1, 3}

예제 출력

8

설명

요소 2, 5, 7, 1, 4, 5, 1, 3은 각각 자신이 속한 행 또는 열에서 최댓값 혹은 최솟값에 해당하므로 모두 위치 요소입니다. 따라서 결과는 8개입니다.

해결 접근 방법

가장 간단한 해결 방법은 다음과 같습니다.

1. 배열을 한 번 순회하면서 각 행의 최댓값과 최솟값, 그리고 각 열의 최댓값과 최솟값을 미리 계산하여 저장합니다.
2. 이후 배열 전체를 다시 탐색하면서 각 요소가 해당 행 또는 열의 최댓값/최솟값 중 하나와 일치하는지 확인하고, 일치한다면 카운트를 증가시킵니다.

이 방법의 시간 복잡도는 O(m × n)으로, 두 번의 선형 순회만 필요하기 때문에 효율적입니다.

C++ 구현 예제

#include <iostream>
using namespace std;
const int MAX = 100;
int countAllPositionalElements(int mat[][MAX], int m, int n){
    int rowmax[m], rowmin[m];
    int colmax[n], colmin[n];
    // 각 행의 최댓값과 최솟값 계산
    for (int i = 0; i < m; i++) {
        int rminn = 10000;
        int rmaxx = -10000;
        for (int j = 0; j < n; j++) {
            if (mat[i][j] > rmaxx)
                rmaxx = mat[i][j];
            if (mat[i][j] < rminn)
                rminn = mat[i][j];
        }
        rowmax[i] = rmaxx;
        rowmin[i] = rminn;
    }
    // 각 열의 최댓값과 최솟값 계산
    for (int j = 0; j < n; j++) {
        int cminn = 10000;
        int cmaxx = -10000;
        for (int i = 0; i < m; i++) {
            if (mat[i][j] > cmaxx)
                cmaxx = mat[i][j];
            if (mat[i][j] < cminn)
                cminn = mat[i][j];
        }
        colmax[j] = cmaxx;
        colmin[j] = cminn;
    }
    // 위치 요소 개수 세기
    int positionalCount = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((mat[i][j] == rowmax[i]) || (mat[i][j] == rowmin[i]) ||
                (mat[i][j] == colmax[j]) || (mat[i][j] == colmin[j])){
                positionalCount++;
            }
        }
    }
    return positionalCount;
}
int main(){
    int mat[][MAX] = {
        { 2, 5, 7 },
        { 1, 3, 4 },
        { 5, 1, 3 }
    };
    int m = 3, n = 3;
    cout<<"Number of positional elements is "<<countAllPositionalElements(mat, m, n);
    return 0;
}

실행 결과

Number of positional elements is 8

마무리

이처럼 각 행과 열의 최댓값·최솟값을 사전에 계산해두면, 이후 단순 비교 연산만으로 위치 요소의 개수를 쉽게 구할 수 있습니다. 하나의 요소가 행과 열 양쪽의 조건을 동시에 만족하는 경우에도 한 번만 카운트되므로, 중복 집계를 걱정할 필요는 없다는 점에 유의하세요.