C++에서 합이 주어진 값 x와 같은 4개의 배열에서 쿼드러플 개수 구하기

네 개의 배열 A[], B[], C[], D[]가 주어졌을 때, A[i] + B[j] + C[k] + D[l] = x를 만족하는 모든 쿼드러플(네 원소 조합)의 개수를 구하는 것이 목표입니다. 네 배열은 모두 동일한 개수의 원소 N개를 가지고 있습니다.

가장 기본적인 방법은 각 배열을 한 번씩 순회하면서 A[i] + B[j] + C[k] + D[l] == x를 만족하는지 확인하고, 조건이 참이면 카운트를 증가시키는 것입니다.

예제를 통해 자세히 이해해 보겠습니다.

입력

A[]={ 1,2,3}; B[]={ 2,3,2}; C[]={ 4,3,1}; D[]={ 3,1,1 }; X=12

출력

쿼드러플의 개수: 4

설명

조건을 만족하는 쿼드러플 (A[i], B[j], C[k], D[l])은 다음과 같습니다:
(2 3 4 3), (3 2 4 3), (3 3 3 3), (3 2 4 3)
총 쿼드러플의 개수 : 4

입력

A[]={ 1,1,1}; B[]={ 2,2,2}; C[]={ 3,3,3}; D[]={ 4,4,4 }; X=15

출력

쿼드러플의 개수: 0

설명

합이 15가 되는 원소 조합이 존재하지 않습니다.

프로그램에 사용된 접근 방식

• 동일한 길이를 가진 정수 배열 A[], B[], C[], D[]를 임의의 값으로 초기화하여 준비합니다.

• 배열의 길이를 저장할 변수 N을 선언합니다.

• 함수 countQuad(int a[], int b[], int c[], int d[], int x, int n)는 네 개의 배열과 그 길이 n, 목표값 x를 입력받아 쿼드러플의 개수를 반환합니다.

• 각 배열을 순회하기 위해 네 개의 중첩 반복문을 사용합니다.

• 가장 바깥쪽 반복문은 a[]를 위한 0<=i<n, 안쪽으로 각각 b[]를 위한 0<=j<n, c[]를 위한 0<=k<n, 가장 안쪽 반복문은 d[]를 위한 0<=l<n 범위로 실행됩니다.

• a[i] + b[j] + c[k] + d[l] == x인지 비교하고, 참이면 카운트를 증가시킵니다.

• 모든 반복문이 종료되면 count에는 합이 x가 되는 쿼드러플의 개수가 저장됩니다.

• count를 결과로 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int countQuads(int a[],int b[],int c[],int d[],int x, int n){
    int count = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                for (int l = 0; l < n; l++){
                    int sum=a[i]+b[j]+c[k]+d[l];
                    if(sum==x){
                        count++;
                        cout<<endl<<a[i]<<" "<<b[j]<<" "<<c[k]<<" "<<d[l];}
                }
            }
        }
    }
    return count;
}
int main(){
    int A[]={ 1,1,1}; int B[]={ 2,2,2}; int C[]={ 3,3,3}; int D[]={ 4,4,4 };
    int X=15;
    int N=3; // 각 배열의 길이
    cout <<endl<< "쿼드러플의 개수 : "<<countQuads(A,B,C,D,X,N);
    return 0;
}

출력 결과

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

쿼드러플의 개수 : 0

이 방법은 네 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(N⁴)입니다. 배열의 크기가 커질 경우 해시 맵을 활용한 최적화 기법으로 성능을 개선할 수 있습니다.