세 개의 배열 A[], B[], C[]가 주어졌을 때, A[i] < B[j] < C[k] 조건을 만족하는 모든 트리플렛(triplet, 세 쌍)의 개수를 구하는 것이 목표입니다. 세 배열은 모두 동일한 개수의 원소 N개를 가지고 있습니다.
가장 기본적인 방법은 세 배열을 각각 한 번씩 순회하면서 A[i] < B[j] 이고 B[j] < C[k] 인지 비교하고, 조건이 참이면 카운트를 증가시키는 것입니다.
예제를 통해 자세히 살펴보겠습니다.
예제 1
입력 −
A[] = {1, 4, 5}, B[] = {0, 2, 3}, C[] = {0, 6, 7}출력 − 트리플렛 개수: 4
설명 −
A[i] < B[j] < C[k]를 만족하는 트리플렛 (1, 2, 6), (1, 2, 7), (1, 3, 6), (1, 3, 7) → 총 4개
예제 2
입력 −
A[] = {7, 8, 9}, B[] = {4, 5, 6}, C[] = {1, 2, 3}출력 − 트리플렛 개수: 0
설명 −
A[i] < B[j] < C[k]를 만족하는 트리플렛이 하나도 없음
접근 방법
동일한 길이를 가진 정수 배열 A[], B[], C[]를 임의의 숫자로 초기화하여 준비합니다.
배열의 길이를 저장할 변수 N을 선언합니다.
countTriplets(int a[], int b[], int c[], int n) 함수는 세 배열과 공통 길이 n을 입력받아 주어진 조건을 만족하는 트리플렛의 개수를 반환합니다.
세 개의 중첩 반복문을 사용하여 각 배열을 순회합니다.
가장 바깥쪽 반복문(0 ≤ i < n)은 a[], 중간 반복문(0 ≤ j < n)은 b[], 가장 안쪽 반복문(0 ≤ k < n)은 c[]를 담당합니다.
a[i] < b[j] 이고 b[j] < c[k] 인지 비교하고, 조건이 참이면 count를 1 증가시킵니다.
모든 반복문이 종료되면 count에는 조건을 만족하는 트리플렛의 총 개수가 저장됩니다.
count를 결과값으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int a[], int b[], int c[], 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++){
if(a[i]<b[j] && b[j]<c[k])
{ count++; }
}
}
}
return count;
}
int main(){
int A[]={ 1,2,3}; int B[]={ 2,3,2}; int C[]={ 4,3,1};
int N=3; // 배열의 길이
cout <<endl<< "Number of triplets : "<<countTriplets(A,B,C,N);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Number of triplets : 6
시간 복잡도 분석
위 방법은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(N³)입니다. 따라서 배열의 크기가 커질수록 실행 시간이 빠르게 증가합니다. 더 큰 입력에 대해서는 정렬과 이분 탐색 또는 누적 합(prefix sum) 기법을 활용하면 O(N²) 또는 그 이하로 최적화할 수 있습니다. 다만 이 글에서 소개한 완전 탐색(brute force) 방식은 구현이 단순하고 직관적이라 작은 크기의 배열이나 알고리즘 학습용으로 적합합니다.