C++ 배열에서 양수·음수로 이루어진 모든 쌍 찾아 출력하기

문제 개요

이 문제에서는 중복 없는 고유한 정수로 구성된 배열이 주어집니다. 목표는 배열 안에서 서로 부호만 반대인 양수와 음수 쌍을 모두 찾아 출력하는 것입니다.

예시를 통해 문제를 좀 더 구체적으로 살펴보겠습니다.

입력: array = {1, 4, 7, -1, 2, 5, -7}
출력: (-1, 1), (-7, 7)

접근 방법

1. 단순한 방법 — 두 개의 반복문 사용

가장 직관적인 해결책은 두 개의 중첩 반복문을 사용해 양수와 음수가 대응되는 쌍을 일일이 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)(n은 배열의 크기)에 달해 배열의 크기가 커질수록 실행 속도가 급격히 느려지므로 비효율적입니다.

2. 효율적인 방법 — 정렬 후 이진 탐색 활용

더 나은 성능을 얻으려면 다음과 같은 순서로 문제를 해결할 수 있습니다.

먼저 배열을 오름차순으로 정렬합니다. 정렬이 끝나면 음수들이 배열의 앞쪽에 모이게 되므로, 각 음수마다 절댓값이 같은 양수가 배열에 존재하는지 이진 탐색(binary search)으로 빠르게 확인할 수 있습니다. 탐색 과정에서 발견된 쌍들을 출력하고, 만약 하나의 쌍도 발견되지 않았다면 그 사실을 사용자에게 알려줍니다.

이 방법의 전체 시간 복잡도는 정렬에 O(n log n), 각 음수에 대한 이진 탐색에 O(log n)이 소요되어 O(n log n)이 되며, 단순 반복문 방식(O(n²))보다 훨씬 효율적입니다.

구현 예제

위에서 설명한 방법을 C++ 코드로 구현한 예시는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
void positiveNegativePair(int arr[], int n);
int main(){
    int arr[] = { 1, 4, 6 , 3, -1, -2, 5, -6, -5 , 8 };
    int n = 10;
    cout<<"Positive Negative pairs in the array are :\n";
    positiveNegativePair(arr, n);
    return 0;
}
void positiveNegativePair(int arr[], int n){
    bool pair_exists = false;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            if (binary_search(arr, arr + n, -arr[i])) {
                cout<<arr[i]<<", "<<-arr[i]<<"\t";
                pair_exists = true;
            }
        }
        else
            break;
    }
    if (!pair_exists)
        cout << "No positive-negative pairs exist in the array";
}

실행 결과

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

-6, 6 -5, 5 -1, 1

정렬된 배열에서 음수(-6, -5, -2, -1)를 차례대로 확인하며, 각 음수의 절댓값에 해당하는 양수가 실제로 배열에 존재할 때만 해당 쌍을 출력합니다. 예제 배열 {1, 4, 6, 3, -1, -2, 5, -6, -5, 8}에는 -2에 대응하는 2가 없기 때문에 (-2, 2) 쌍은 결과에 포함되지 않습니다.