C++로 정수 배열에서 최대 곱을 가지는 쌍 찾기

배열 A에 n개의 서로 다른 원소가 있다고 가정해 봅시다. 우리의 목표는 배열 A에서 두 원소의 곱이 최대가 되는 쌍 (x, y)을 찾는 것입니다. 이때 배열에는 양수와 음수가 함께 포함될 수 있습니다.

예를 들어 배열이 A = [-1, -4, -3, 0, 2, -5]와 같다면, 최대 곱을 만드는 쌍은 (-4, -5)입니다. 두 음수를 곱하면 양수가 되며, 그 결과인 20이 이 배열에서 만들 수 있는 최대 곱이기 때문입니다.

문제 해결 접근 방식

이 문제를 효율적으로 해결하려면 배열을 한 번만 순회하면서 다음 네 가지 값을 추적해야 합니다.

• pos_max: 가장 큰 양수
• pos_second_max: 두 번째로 큰 양수
• neg_max: 절댓값이 가장 큰 음수
• neg_second_max: 절댓값이 두 번째로 큰 음수

배열 순회가 끝나면 (neg_max × neg_second_max)와 (pos_max × pos_second_max)를 비교합니다. 음수 쌍의 곱이 더 크면 음수 쌍을 반환하고, 그렇지 않으면 양수 쌍을 반환합니다. 이 방법의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
void maxProdPair(int arr[], int n) {
    if (n < 2) {
        cout << "No pair is present";
        return;
    }
    if (n == 2) {
        cout << "(" << arr[0] << ", " << arr[1] << ")" << endl;
        return;
    }
    int pos_max = INT_MIN, pos_second_max = INT_MIN;
    int neg_max = INT_MIN, neg_second_max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > pos_max) {
            pos_second_max = pos_max;
            pos_max = arr[i];
        } else if (arr[i] > pos_second_max)
            pos_second_max = arr[i];
        if (arr[i] < 0 && abs(arr[i]) > abs(neg_max)) {
            neg_second_max = neg_max;
            neg_max = arr[i];
        }
        else if(arr[i] < 0 && abs(arr[i]) > abs(neg_second_max))
            neg_second_max = arr[i];
    }
    if (neg_max*neg_second_max > pos_max*pos_second_max)
        cout << "(" << neg_max << ", " << neg_second_max << ")" << endl;
    else
        cout << "(" << pos_max << ", " << pos_second_max << ")" << endl;
}
int main() {
    int arr[] = {-1, -4, -3, 0, 2, -5};
    int n = sizeof(arr)/sizeof(arr[0]);
    maxProdPair(arr, n);
}

실행 결과

(-5, -4)

코드 동작 설명

위 코드는 먼저 배열의 크기가 2 미만일 경우 쌍이 존재하지 않는다고 출력하고 종료합니다. 크기가 정확히 2라면 해당 두 원소가 유일한 쌍이므로 바로 출력합니다.

그 외의 경우에는 반복문을 통해 각 원소를 확인하면서 양수 중 가장 큰 두 값과, 음수 중 절댓값이 가장 큰 두 값을 갱신합니다. 모든 원소를 확인한 뒤 두 곱을 비교하여 더 큰 곱을 가진 쌍을 출력합니다.

예제 입력 [-1, -4, -3, 0, 2, -5]에서는 양수 쌍의 최대 곱이 2 × 0 = 0이지만, 음수 쌍의 최대 곱은 (-5) × (-4) = 20으로 더 크므로 (-5, -4)가 결과로 출력됩니다.