숫자 배열 Arr[]가 주어졌을 때, 곱이 주어진 수 p와 같은 삼중항(triplet)의 개수를 세는 것이 목표입니다. 값이 같더라도 서로 다른 요소로 이루어진 삼중항은 별개로 계산합니다. 예를 들어 배열 [1,2,3,1,2]에서 (1,2,3)과 (3,1,2)는 값은 같지만 사용된 요소가 다르므로 서로 다른 삼중항으로 셉니다.
예제로 이해하기
입력 − arr[]= { 1,2,3,2,4,1,5 }, p=4
출력 − 삼중항 개수: 3
설명 −
삼중항 1 [ 1,2,3,2,4,1,5 ] → (1,2,2), 곱 = 4 삼중항 2 [ 1,2,3,2,4,1,5 ] → (1,4,1), 곱 = 4 삼중항 3 [ 1,2,3,2,4,1,5 ] → (2,2,1), 곱 = 4 곱이 4인 삼중항은 총 3개입니다.
입력 − arr[]= { 1,1,2,1,2,2 }, p=8
출력 − 삼중항 개수: 1
설명 −
삼중항 1 [ 1,1,2,1,2,2 ] → (2,2,2), 곱 = 8 곱이 8인 삼중항은 총 1개입니다.
접근 방식
임의의 숫자로 초기화된 정수 배열 Arr[]를 사용합니다.
변수 product에는 목표 곱 값을, N에는 배열의 길이를 저장합니다.
함수 countTriplets(int arr[], int n, int p)는 배열, 배열 길이, 목표 곱을 입력으로 받아 곱이 p와 같은 삼중항의 개수를 반환합니다.
삼중항의 개수를 세기 위한 변수 count를 0으로 초기화합니다.
각 삼중항의 곱을 저장할 변수 prod를 1로 초기화합니다.
세 개의 for 루프를 중첩하여 삼중항을 구성하는 세 요소를 모두 탐색합니다.
가장 바깥쪽 루프는 0 ≤ i < n-2, 중간 루프는 i < j < n-1, 가장 안쪽 루프는 j < k < n 범위로 실행합니다.
prod = arr[i] * arr[j] * arr[k]를 계산한 뒤, prod == p라면 count를 1 증가시킵니다.
모든 루프가 종료되면 count에는 조건을 만족하는 삼중항의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[],int n,int p){
int count = 0;
int prod=1;
for (int i = 0; i < n-2; i++){
for (int j = i+1; j < n-1; j++){
for (int k = j+1; k < n; k++){
prod=arr[i]*arr[j]*arr[k];
if ( prod==p ){
count++;
// cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; // 출력용
}
}
}
}
return count;
}
int main(){
int Arr[]={ 1,2,3,6,1,6,3,2,1};
int N=9; // 배열 길이
int product=6;
cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N,product);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Number of triplets : 18.
시간 복잡도
세 개의 루프를 중첩해 모든 가능한 조합을 확인하므로 시간 복잡도는 O(n³)입니다. 배열의 크기가 작을 때는 충분히 효율적이지만, 배열이 커질 경우 해시맵 등을 활용한 최적화를 고려할 수 있습니다. 또한 이 방법은 값이 같은 요소라도 인덱스가 다르면 모두 별개의 삼중항으로 계산한다는 점에 유의해야 합니다.