길이가 n인 정수 배열 Arr[]와 목표값 M이 주어졌을 때, 배열에서 서로 다른 세 원소를 곱한 값이 M과 같아지는 조합(삼중항, triplet)의 개수를 구하는 것이 이 문제의 목표입니다. 배열에는 양의 정수만 포함되어 있다고 가정합니다.
가장 직관적인 풀이 방법은 세 개의 for 루프를 중첩하여 가능한 모든 인덱스 조합(i < j < k)을 확인하는 것입니다. 각 조합에 대해 arr[i] * arr[j] * arr[k] == M을 만족하면 카운트를 1씩 증가시키고, 모든 탐색이 끝난 후 카운트 값을 반환하면 됩니다.
예제로 이해하기
입력
arr[] = { 1, 2, 3, 0, 2, 4 }, M = 24출력
곱이 M인 삼중항의 개수: 2
설명
곱이 24가 되는 삼중항은 다음과 같습니다.
(2, 3, 4) → 2 × 3 × 4 = 24
(3, 2, 4) → 3 × 2 × 4 = 24
총 삼중항 개수: 2
입력
arr[] = { 2, 2, 2, 2, 2 }, M = 6출력
곱이 M인 삼중항의 개수: 0
설명
배열의 모든 원소가 2이므로 어떤 삼중항의 곱도 2 × 2 × 2 = 8이 됩니다.
M = 6을 만족하는 삼중항은 없습니다.
총 삼중항 개수: 0
접근 방법
- 임의의 숫자로 초기화된 정수 배열 Arr[]를 준비합니다.
- 변수 N에는 배열 Arr[]의 길이를 저장합니다.
- productisM(int arr[], int n, int m) 함수는 배열과 그 길이를 매개변수로 받아, 곱이 m과 같은 삼중항의 개수를 반환합니다.
- 삼중항의 개수를 저장할 변수 count를 0으로 초기화합니다.
- 세 개의 중첩된 for 루프를 사용하여 삼중항을 구성하는 각 원소를 탐색합니다.
- 가장 바깥쪽 루프는 0 ≤ i < n-2, 중간 루프는 i < j < n-1, 가장 안쪽 루프는 j < k < n 범위로 실행하여 동일한 인덱스가 중복 선택되지 않도록 합니다.
- 각 조합에 대해 arr[i] * arr[j] * arr[k] == m인지 검사하고, 조건이 참이면 count를 증가시킵니다.
- 모든 루프가 종료되면 count에는 조건을 만족하는 삼중항의 총 개수가 저장됩니다.
- count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int productisM(int arr[], int n, int m){
int count = 0;
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++){
int prod = arr[i]*arr[j]*arr[k];
if(prod == m)
{ count++; }
}
}
}
return count;
}
int main(){
int Arr[] = { 1,2,3,0,2,4 };
int N = 6; // 배열의 길이
int M = 24;
cout << endl << "Number of triplets with product M : " << productisM(Arr,N,M);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Number of triplets with product M : 2
복잡도 분석
세 개의 루프를 중첩해 사용하므로 시간 복잡도는 O(n³)입니다. 배열의 길이가 커질수록 연산 횟수가 급격히 늘어나므로, 입력 크기가 작은 경우에 적합한 방법입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.