정수 배열 Arr[]와 범위를 정의하는 두 변수 a, b가 주어졌을 때, 세 원소의 합이 이 범위 [a, b] 사이에 속하는 삼중항(triplet)의 개수를 찾는 것이 목표입니다.
가장 직관적인 방법은 세 개의 for 루프를 사용하는 것입니다. arr[i]+arr[j]+arr[k] >= a 이면서 arr[i]+arr[j]+arr[k] <= b 조건을 만족하면 카운트를 증가시킵니다. 이때 인덱스는 0 <= i <= n-2, i < j < n-1, j < k < n을 따르며, n은 배열 Arr[]의 원소 개수입니다.
예제로 이해하기
입력 예시 1
입력 − arr[] = { 1, 2, 3, 4, 5 }, N = 5, L = 2, R = 8
출력 − 삼중항 개수 − 4
설명 −
합이 2 이상 8 이하인 삼중항
(1,2,3) → 6
(1,2,4) → 7
(1,2,5) → 8
(1,3,4) → 8
총 삼중항 개수: 4
입력 예시 2
입력 − arr[] = { 2, 2, 2, 2, 2 }, N = 5, L = 2, R = 5
출력 − 삼중항 개수 − 0
설명 −
모든 삼중항의 합은 6으로, 범위 [2, 5]에 속하지 않습니다.
총 삼중항 개수: 0
프로그램에 적용한 접근 방식
무작위 숫자로 초기화된 정수 배열 Arr[]를 준비합니다.
범위 [L, R]을 정의하기 위해 변수 L과 R을 사용하고, N에는 배열 Arr[]의 길이를 저장합니다.
함수 countTriplets(int arr[], int n, int a, int b)는 배열, 배열의 길이, 범위 변수를 입력으로 받아 합이 해당 범위에 속하는 삼중항의 개수를 반환합니다.
삼중항 개수를 저장할 변수 count를 0으로 초기화합니다.
각 삼중항의 합을 저장할 변수 sum을 초기값 0으로 선언합니다.
세 개의 for 루프를 사용해 삼중항의 각 원소를 순회합니다.
가장 바깥쪽 루프는 0 <= i < n-2, 중간 루프는 i < j < n-1, 가장 안쪽 루프는 j < k < n 범위로 실행됩니다.
sum = arr[i] + arr[j] + arr[k]를 계산한 뒤, a <= sum <= b 조건을 만족하면 count를 증가시킵니다.
모든 루프가 종료되면 count에는 조건을 만족하는 삼중항의 총 개수가 저장됩니다.
count를 결과값으로 반환합니다.
이 방법의 시간 복잡도는 세 개의 중첩 루프로 인해 O(n³)이며, 추가 공간 없이 동작하므로 공간 복잡도는 O(1)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[],int n,int a,int b){
int count = 0;
int sum=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++){
sum=arr[i]+arr[j]+arr[k];
if ( sum>=a && sum<=b) //조건 검사{
count++;
// cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; //출력용
}
}
}
}
return count;
}
int main(){
int Arr[]={ 5,4,3,6,8,2 };
int L=9;
int R=15;
int N=6; //배열의 길이
cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N,L,R);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Number of triplets : 14