C++로 정렬된 배열에서 곱이 k보다 작은 쌍의 개수 세기

정수형 요소로 이루어진 정렬된 배열과 정수 변수 k가 주어졌을 때, 배열에서 서로 다른 두 요소를 짝지어 만들 수 있는 모든 쌍(pair)을 구하고, 각 쌍의 곱이 k보다 작은지 판별하여 해당하는 쌍의 개수를 세는 것이 이번 문제의 목표입니다.

예제 1

입력

int arr[] = {2, 7, 1, 0, 8}, int k = 10

출력

곱이 k보다 작은 쌍의 개수: 7

설명: 주어진 배열에서 만들 수 있는 쌍은 다음과 같습니다.
(2, 7) = 14 → k보다 큼
(2, 1) = 2 → k보다 작음 ✔
(2, 0) = 0 → k보다 작음 ✔
(2, 8) = 16 → k보다 큼
(7, 1) = 7 → k보다 작음 ✔
(7, 0) = 0 → k보다 작음 ✔
(7, 8) = 56 → k보다 큼
(1, 0) = 0 → k보다 작음 ✔
(1, 8) = 8 → k보다 작음 ✔
(0, 8) = 0 → k보다 작음 ✔
따라서 곱이 k보다 작은 쌍은 총 7개입니다.

예제 2

입력

int arr[] = {2, 4, 6, 8}, int k = 10

출력

곱이 k보다 작은 쌍의 개수: 1

설명: 만들 수 있는 쌍은 (2, 4) = 8(k보다 작음 ✔), (2, 6) = 12, (2, 8) = 16, (4, 6) = 24, (4, 8) = 32, (6, 8) = 48이며, 나머지는 모두 k보다 큽니다. 따라서 조건을 만족하는 쌍은 1개뿐입니다.

해결 접근 방법

이 문제는 여러 가지 방식으로 해결할 수 있습니다. 먼저 직관적인 무차별 대입(Brute Force) 방식을 살펴본 후, 시간 복잡도를 크게 줄일 수 있는 투 포인터(Two Pointer) 방식을 알아보겠습니다.

방법 1: 무차별 대입 방식 (Brute Force)

정수 배열을 입력받고 배열의 크기를 계산한 후 함수로 전달합니다.
곱이 k보다 작은 쌍의 개수를 저장할 변수 count를 선언합니다.
i를 0부터 배열 끝까지 반복하는 외부 루프를 실행합니다.
내부에서는 j를 i+1부터 배열 끝까지 반복하는 중첩 루프를 실행하여 모든 쌍을 검사합니다.
각 쌍의 곱 arr[i] * arr[j]가 k보다 작으면 count를 1 증가시킵니다.
최종적으로 count를 반환하고 결과를 출력합니다.

이 방식은 모든 쌍을 일일이 확인하므로 시간 복잡도는 O(n²)입니다.

방법 2: 효율적인 방식 (Two Pointer)

정수 배열을 입력받고 배열의 크기를 계산한 후 함수로 전달합니다.
쌍의 개수를 저장할 변수 count를 선언합니다.
왼쪽 포인터 arr_0을 0으로, 오른쪽 포인터 arr_1을 size-1로 설정합니다.
arr_0 < arr_1인 동안 WHILE 루프를 반복합니다.
만약 arr[arr_0] * arr[arr_1] < k라면, 배열이 정렬되어 있으므로 arr_0과 arr_1 사이의 모든 요소와의 곱도 k보다 작습니다. 따라서 count += (arr_1 - arr_0)으로 한 번에 더하고 arr_0을 증가시킵니다. 그렇지 않으면 arr_1을 1 감소시킵니다.
최종적으로 count를 반환하고 결과를 출력합니다.

배열이 이미 정렬되어 있다는 조건을 활용하기 때문에 시간 복잡도는 단 O(n)으로, 훨씬 빠르게 동작합니다.

예제 코드 (무차별 대입 방식)

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

출력 결과

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

Count of pairs in a sorted array whose product is less than k are: 5

예제 코드 (투 포인터 방식)

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

출력 결과

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

Count of pairs in a sorted array whose product is less than k are: 10

마무리

정렬된 배열에서 곱이 특정 값보다 작은 쌍을 찾는 문제는 무차별 대입 방식으로도 충분히 해결할 수 있지만, 데이터의 크기가 커질수록 O(n²)의 성능 한계가 드러납니다. 배열이 정렬되어 있다는 특성을 활용한 투 포인터 기법은 탐색 범위를 효율적으로 좁혀 O(n)의 시간 안에 답을 구할 수 있으므로, 실전 코딩 테스트에서는 후자의 접근 방식을 사용하는 것이 좋습니다.