C++에서 합이 x보다 작은 정렬 배열의 쌍 개수 구하기

문제 소개

정렬된 정수형 배열 하나와 정수 변수 x가 주어졌을 때, 배열의 원소들로 만들 수 있는 모든 쌍(pair) 중에서 두 원소의 합이 x보다 작은 쌍이 몇 개인지 계산하는 것이 이번 글의 목표입니다.

예제 1

입력 : int arr[] = {2, 7, 1, 0, 8}, int x = 8

출력 : 합이 x보다 작은 쌍의 개수 − 4

설명 : 주어진 배열에서 만들 수 있는 쌍과 그 합은 다음과 같습니다.
(2, 7) = 9 (x보다 큼), (2, 1) = 3 (x보다 작음), (2, 0) = 2 (x보다 작음), (2, 8) = 10 (x보다 큼)
(7, 1) = 8 (x와 같음), (7, 0) = 7 (x보다 작음), (7, 8) = 15 (x보다 큼)
(1, 0) = 1 (x보다 작음), (1, 8) = 8 (x와 같음), (0, 8) = 8 (x와 같음)
따라서 합이 x보다 작은 쌍은 (2, 1), (2, 0), (7, 0), (1, 0)으로 총 4개입니다.

예제 2

입력 : int arr[] = {2, 4, 6, 8}, int x = 10

출력 : 합이 x보다 작은 쌍의 개수 − 2

설명 : 만들 수 있는 쌍은 (2, 4) = 6 (x보다 작음), (2, 6) = 8 (x보다 작음), (2, 8) = 10 (x와 같음), (4, 6) = 10 (x와 같음), (4, 8) = 12 (x보다 큼), (6, 8) = 14 (x보다 큼)입니다. 따라서 조건을 만족하는 쌍은 2개입니다.

풀이 접근 방법

이 문제는 단순한 완전 탐색(브루트 포스) 방식과 효율적인 투 포인터(Two Pointer) 방식, 두 가지 방법으로 해결할 수 있습니다. 먼저 완전 탐색 방법부터 살펴보겠습니다.

1. 완전 탐색(브루트 포스) 접근

정수 배열을 입력받아 배열의 크기를 계산한 후 함수에 전달합니다.
합이 x보다 작은 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
i를 0부터 배열 크기까지 반복하는 바깥쪽 FOR 루프를 시작합니다.
루프 내부에서 j를 i + 1부터 배열 크기까지 반복하는 안쪽 FOR 루프를 시작합니다.
sum = arr[i] + arr[j]를 계산하고, sum < x이면 count를 1 증가시킵니다.
count를 반환하고 결과를 출력합니다.

이 방식은 모든 가능한 쌍을 하나씩 검사하므로 시간 복잡도는 O(n²)입니다.

2. 투 포인터(효율적) 접근

정수 배열을 입력받아 배열의 크기를 계산한 후 함수에 전달합니다.
임시 변수 count를 선언합니다.
왼쪽 포인터 arr_0을 0으로, 오른쪽 포인터 arr_1을 size - 1로 설정합니다.
arr_0 < arr_1 동안 WHILE 루프를 반복합니다.
루프 안에서 arr[arr_0] + arr[arr_1] < x이면 count에 (arr_1 - arr_0)을 더한 후 arr_0을 1 증가시키고, 그렇지 않으면 arr_1을 1 감소시킵니다.
count를 반환하고 결과를 출력합니다.

배열이 정렬되어 있기 때문에 이 방법이 동작합니다. 가장 작은 값(arr[arr_0])과 가장 큰 값(arr[arr_1])의 합이 x보다 작다면, 그 사이에 있는 모든 값과의 조합 역시 합이 x보다 작으므로 한 번에 (arr_1 - arr_0)개의 쌍을 카운트할 수 있습니다. 시간 복잡도는 O(n)으로 훨씬 효율적입니다.

예제 코드 (완전 탐색)

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
    int count = 0;
    int sum = 0;
    for(int i = 0 ; i < size ; i++){
        for(int j = i+1; j < size; j++){
            sum = arr[i] + arr[j];
            if(sum < x){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {2, 7, 1, 0, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 8;
    cout << "Count of pairs in a sorted array whose sum is less than x are: " << pair_sum(arr, size, x);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of pairs in a sorted array whose sum is less than x are: 4

예제 코드 (투 포인터)

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
    int arr_0 = 0;
    int arr_1 = size - 1;
    int count = 0;
    while(arr_0 < arr_1){
        if (arr[arr_0] + arr[arr_1] < x){
            count = count + (arr_1 - arr_0);
            arr_0++;
        }
        else{
            arr_1--;
        }
    }
    return count;
}
int main(){
    int arr[] = {2, 7, 1, 0, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 8;
    cout << "Count of pairs in a sorted array whose sum is less than x are: " << pair_sum(arr, size, x);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of pairs in a sorted array whose sum is less than x are: 4

마무리

두 원소의 합이 특정 값보다 작은 쌍의 개수를 구할 때는 배열이 정렬되어 있다는 조건만 활용해도 성능을 크게 개선할 수 있습니다. 데이터 크기가 클수록 투 포인터 기법(O(n))이 완전 탐색(O(n²))보다 압도적으로 유리하므로, 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.