C++로 배열에서 x < y를 만족하는 쌍(x, y)의 개수 구하기

문제 소개

정수 배열이 주어졌을 때, 배열의 원소들을 사용하여 만들 수 있는 모든 순서쌍 (x, y) 중에서 x가 y보다 작은 조건을 만족하는 쌍의 총 개수를 구하는 것이 목표입니다.

입력 − int arr[] = { 2, 4, 3, 1 }

출력 − x < y를 만족하는 배열 내 쌍(x, y)의 개수: 6

설명 − 배열 { 2, 4, 3, 1 }에서 만들 수 있는 모든 순서쌍은 아래 표와 같습니다.

표에서 조건을 만족하는 쌍은 (2, 4), (2, 3), (1, 2), (3, 4), (1, 4), (1, 3)으로 총 6개임을 확인할 수 있습니다.

알고리즘 접근 방법

• 쌍을 만들 정수 배열을 입력받습니다.
• 배열의 크기를 계산한 후, 이후 처리를 위해 함수에 데이터를 전달합니다.
• x가 y보다 작은 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
• i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
• 루프 안에서 j를 0부터 배열 크기까지 반복하는 또 다른 FOR 루프를 시작합니다.
• 루프 안에서 IF arr[i] < arr[j]가 참이면 count를 1 증가시킵니다.
• count 값을 반환합니다.
• 결과를 출력합니다.

예제 코드

#include <iostream>
using namespace std;
int X_Less_Y(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        for (int j = 0; j < size; j++){
            if (arr[i] < arr[j]){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 2, 4, 3, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs (x, y) in an array such that x < y are: "<<X_Less_Y(arr, size);
    return 0;
}

실행 결과

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

Count of pairs (x, y) in an array such that x < y are: 6

시간 복잡도

위 방법은 두 개의 중첩 루프를 사용하므로 시간 복잡도는 O(n²)입니다. 따라서 배열의 크기가 커질수록 실행 시간이 급격히 늘어날 수 있습니다. 성능을 개선하려면 배열을 먼저 정렬한 뒤, 각 원소보다 큰 원소의 개수를 이분 탐색으로 찾는 방식(O(n log n))을 활용하면 효율적으로 문제를 해결할 수 있습니다.