C++로 배열에서 절댓값이 같은 양수·음수 쌍 찾기

이 글에서는 서로 중복되지 않는(distinct) 요소들로 구성된 배열이 주어졌을 때, 절댓값이 같은 양수와 음수 쌍을 찾아 정렬된 순서로 출력하는 문제를 다룹니다.

입력 : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 }
출력 : -1 1 -12 12 -56 56

입력 : arr[] = {30, 40, 50, 77, -51, -50, -40}
출력 : -40 40 -50 50

문제 해결 접근 방법

가장 먼저 떠오르는 방법은 브루트 포스(Brute Force, 완전 탐색) 방식이며, 여기에 더해 시간 복잡도를 크게 줄일 수 있는 효율적인 방식도 있습니다. 지금부터 두 가지 방식을 모두 자세히 살펴보겠습니다.

브루트 포스(완전 탐색) 방식

이 방식에서는 배열을 한 인덱스씩 순회하면서, 현재 요소와 절댓값은 같지만 위치가 다른(즉, 부호만 반대인) 요소를 찾습니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
   int n = sizeof(arr)/sizeof(int); // 배열의 크기
   vector<int> nums; // 발견된 쌍의 값을 저장

   for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
         if(abs(arr[j]) == abs(arr[i])) { // 절댓값이 같은 쌍을 찾으면
            nums.push_back(abs(arr[i]));
            break;
            // 쌍을 찾았으므로 내부 반복문을 종료합니다.
            // 배열의 요소들은 중복되지 않으므로 안전합니다.
         }
      }
   }
   sort(nums.begin(), nums.end());
   for(auto x : nums) // 쌍을 출력
      cout << -x << " " << x << " ";
}

출력 결과

-1 1 -12 12 -56 56

이 방식은 두 개의 반복문으로 배열을 순회하며 짝이 되는 다른 요소를 찾습니다. 짝을 찾으면 내부 반복문을 break로 즉시 빠져나가 실행 속도를 조금이라도 높입니다. 하지만 이중 반복문을 사용하기 때문에 전체 시간 복잡도는 O(N²)입니다(N은 배열의 크기). 제약 조건이 작은 경우에는 충분하지만, 입력 크기가 커지면 비효율적입니다. 그렇다면 더 나은 방법을 살펴보겠습니다.

효율적인 방식: 해시맵(Hashing) 활용

이 방식에서는 해시맵을 사용해 시간 복잡도를 크게 줄입니다. 핵심 아이디어는 각 숫자의 절댓값별 빈도를 기록하는 것입니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
   int n = sizeof(arr)/sizeof(int); // 배열의 크기
   map<int, int> found; // 절댓값별 등장 횟수를 저장
   vector<int> nums; // 발견된 쌍의 값을 저장

   for(int i = 0; i < n; i++)
      found[abs(arr[i])]++; // abs(arr[i])의 빈도를 증가

   for(auto x : found) { // 맵을 순회하며
      if(x.second == 2) // 빈도가 2인 값(=쌍이 존재하는 값)을 저장
         nums.push_back(x.first);
   }
   for(auto x : nums) // 쌍을 출력
      cout << -x << " " << x << " ";
}

출력 결과

-1 1 -4 4 -8 8 -9 9

코드 설명

이 방식에서는 해시맵(std::map)을 사용해 각 숫자의 빈도를 저장합니다. 배열을 순회하면서 현재 요소의 절댓값에 해당하는 빈도를 계속 업데이트합니다. 어떤 절댓값의 빈도가 2라는 것은 양수와 음수가 모두 존재한다는 의미이므로, 이후 맵을 순회하며 빈도가 2인 숫자만 nums 벡터에 담고 최종적으로 출력합니다.

특히 std::map은 키를 항상 정렬된 상태로 유지하므로, 별도의 정렬 과정 없이 곧바로 정렬된 순서로 결과를 얻을 수 있다는 장점이 있습니다. 이 방식의 시간 복잡도는 std::map 사용 시 O(N log N), unordered_map을 사용하면 평균 O(N)까지 개선할 수 있습니다.

마무리

이 글에서는 해싱 기법을 활용해 배열에서 절댓값이 같은 양수·음수 쌍을 찾는 문제를 해결했습니다. 완전 탐색 방식과 해시맵 기반의 효율적 방식, 두 가지 접근법과 함께 전체 C++ 구현 코드도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.