C++로 행렬 각 열에서 최대 차이를 만드는 요소 쌍 찾기

N×N 크기의 정방행렬이 하나 주어졌다고 가정해 보겠습니다. 이때 해야 할 일은 행렬의 어느 한 열에서든 최대 차이(maximum difference)를 만들어 내는 두 요소의 쌍(pair)을 찾는 것입니다.

예를 들어 다음과 같은 3×3 행렬이 있다고 합시다.

이때 출력 결과는 8입니다. 0번째 열의 (1, 9) 쌍이 9 − 1 = 8이라는 차이를 만들어 내는데, 이것이 모든 열 중에서 가장 큰 차이이기 때문입니다.

접근 방법

핵심 아이디어는 매우 단순합니다. 각 열을 순회하면서 해당 열의 최댓값과 최솟값을 구한 뒤 두 값의 차이를 계산하고, 그중 가장 큰 차이를 반환하면 됩니다.

1. 각 열의 첫 번째 행 값을 초기 최댓값·최솟값으로 설정합니다.
2. 나머지 행을 순회하면서 최댓값과 최솟값을 갱신합니다.
3. (최댓값 − 최솟값)을 기존 최대 차이와 비교하여 더 큰 값으로 갱신합니다.
4. 모든 열에 대한 순회가 끝나면 최종 최대 차이를 반환합니다.

C++ 구현 예제

#include<iostream>
#define N 5
using namespace std;
int maxVal(int x, int y){
    return (x > y) ? x : y;
}
int minVal(int x, int y){
    return (x > y) ? y : x;
}
int colMaxDiff(int mat[N][N]) {
    int diff = INT_MIN;
    for (int i = 0; i < N; i++) {
        int max_val = mat[0][i], min_val = mat[0][i];
        for (int j = 1; j < N; j++) {
            max_val = maxVal(max_val, mat[j][i]);
            min_val = minVal(min_val, mat[j][i]);
        }
        diff = maxVal(diff, max_val - min_val);
    }
    return diff;
}
int main() {
    int mat[N][N] = {{ 1, 2, 3, 4, 5 }, { 5, 3, 5, 4, 0 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 },
{ 9, 7, 12, 4, 3 }};
    cout << "Max difference : " << colMaxDiff(mat) << endl;
}

실행 결과

Max difference : 12

위 예제 행렬에서 마지막 열(인덱스 4)은 {5, 0, 9, 12, 3}으로 구성되어 있으며, 최댓값 12와 최솟값 0의 차이인 12가 전체 최대 차이가 됩니다.

복잡도 분석

• 시간 복잡도: O(N²) — 행렬의 모든 원소를 한 번씩 확인해야 하므로 N×N개 원소를 순회하는 비용이 발생합니다.
• 공간 복잡도: O(1) — 별도의 추가 배열 없이 상수 개수의 변수만 사용합니다.