C++로 배열에서 고유한 쌍의 개수 찾기

개요

C++에서 배열에 존재하는 고유한 쌍(unique pair)의 개수를 구하는 문제는 알고리즘 학습에서 자주 등장하는 주제입니다. 여기서 '고유한 쌍'이란 주어진 배열에서 만들 수 있는 모든 가능한 순서쌍 중 중복되지 않는 쌍을 의미합니다.

예를 들어 다음과 같습니다.

입력 : array[] = { 5, 5, 9 }
출력 : 4
설명 : 고유한 쌍은 (5, 5), (5, 9), (9, 5), (9, 9)로 총 4개입니다.

입력 : array[] = { 5, 4, 3, 2, 2 }
출력 : 16

해결 방법

이 문제를 해결하는 방법은 크게 두 가지가 있습니다. 하나는 직관적인 브루트 포스(Brute Force) 방식이고, 다른 하나는 시간 복잡도를 개선한 효율적인(Efficient) 방식입니다.

방법 1: 브루트 포스 접근법

가장 단순한 방법은 배열에서 만들 수 있는 모든 가능한 쌍을 하나씩 탐색하면서 집합(set)에 저장하는 것입니다. 집합은 자동으로 중복을 제거해 주므로, 최종적으로 집합의 크기를 출력하면 그것이 곧 고유한 쌍의 개수가 됩니다.

이 방법의 시간 복잡도는 O(n² log n)입니다. 이중 반복문으로 모든 쌍을 생성하는 데 O(n²)이 걸리고, 각 삽입마다 set의 정렬 특성상 O(log n)이 추가되기 때문입니다.

코드 예제

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

int main () {
    int arr[] = { 5, 4, 3, 2, 2 };
    int n = sizeof (arr) / sizeof (arr[0]);

    // 쌍을 저장할 집합 선언
    set < pair < int, int >> set_of_pairs;

    // 모든 가능한 쌍을 집합에 삽입
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            set_of_pairs.insert (make_pair (arr[i], arr[j]));

    int result = set_of_pairs.size();

    cout << "Number of unique pairs : " << result;
    return 0;
}

출력 결과

Number of unique pairs : 16

코드 설명

위 코드에서는 먼저 pair를 저장할 set 변수를 선언합니다. 그다음 두 개의 반복문을 사용하여 i와 j 인덱스로 만들 수 있는 모든 순서쌍을 생성하고, make_pair 함수로 쌍을 만들어 집합에 삽입합니다. 집합은 내부적으로 중복 요소를 자동으로 거르기 때문에, 마지막에 size() 함수로 집합의 크기를 계산하여 출력하면 고유한 쌍의 총 개수를 얻을 수 있습니다.

방법 2: 효율적인 접근법

더 효율적인 방법은 핵심 아이디어를 활용하는 것입니다. 즉, 배열에서 서로 다른 값(고유한 숫자)의 개수를 먼저 구하고, 각 고유한 값은 자기 자신을 포함한 모든 고유한 값과 쌍을 이룰 수 있으므로, 고유한 쌍의 개수 = 고유한 숫자 개수의 제곱(n²)이라는 공식이 성립합니다.

중복 제거를 위해 unordered_set을 사용하면 평균적으로 O(1)의 삽입 시간을 보장하며, 전체 시간 복잡도는 O(n)으로 크게 향상됩니다.

코드 예제

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

int main () {
    int arr[] = { 5, 4, 3, 2, 2 };
    int n = sizeof (arr) / sizeof (arr[0]);

    // 고유한 원소를 저장할 집합 선언
    unordered_set < int > set_of_elements;

    // 배열의 모든 원소를 집합에 삽입
    for (int i = 0; i < n; i++)
        set_of_elements.insert (arr[i]);

    int size = set_of_elements.size ();

    // 고유한 쌍의 개수 계산 (n의 제곱)
    int result = size * size;

    cout << "Number of unique pairs in an array: " << result;
    return 0;
}

출력 결과

Number of unique pairs : 16

코드 설명

이 코드에서는 먼저 int형 원소를 저장할 unordered_set을 선언한 후, 배열의 모든 원소를 집합에 삽입하여 중복을 제거합니다. 예제 배열 { 5, 4, 3, 2, 2 }에서 실제 고유한 값은 5, 4, 3, 2의 네 가지입니다. 이후 집합의 크기를 구하고, 공식 n²에 따라 4 × 4 = 16을 계산하여 결과를 출력합니다.

마무리

이번 글에서는 배열에서 고유한 쌍의 개수를 찾는 문제를 두 가지 방식으로 해결해 보았습니다. 첫 번째 브루트 포스 방식은 모든 가능한 쌍을 set에 삽입하는 직관적인 방법으로 시간 복잡도는 O(n² log n)이며, 두 번째 효율적인 방식은 고유한 숫자의 개수를 구한 뒤 n² 공식으로 답을 얻어 O(n)의 시간 복잡도를 달성합니다. 입력 배열의 크기가 클수록 두 번째 방법이 훨씬 유리하다는 점을 기억하시기 바랍니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.