각 크기의 정수 값으로 구성된 arr[] 배열이 주어지고 주어진 배열에서 사용할 수 있는 고유한 쌍의 개수를 계산하고 그 합계도 동일한 배열에 있다고 가정해 보겠습니다.
배열은 같은 유형의 요소에 대한 고정 크기 순차 컬렉션을 저장할 수 있는 일종의 데이터 구조입니다. 배열은 데이터 모음을 저장하는 데 사용되지만 종종 배열을 같은 유형의 변수 모음으로 생각하는 것이 더 유용합니다.
기억해야 할 점
-
한 쌍은 순서와 상관없이 동일한 요소로 한 번 계산됩니다. 예를 들어 (3,2) 및 (2,3)은 1로 계산됩니다.
-
배열에서 여러 번 발생하는 숫자가 있는 경우 한 쌍을 형성하는 데 정확히 두 번 간주됩니다. 예를 들어 배열에 {2, 2, 2, 2}와 같은 요소가 있는 경우 쌍은 (2,2)가 되고 1로 계산됩니다.
예
Input − int arr = {6, 4, 10, 14}
Output − count is 2 설명 - 배열에서 합이 있는 쌍은 (6,4) 및 (10,4)이므로 개수는 2입니다.
Input − int arr = {6, 6, 6 ,6, 6, 13}
Output − count is 0 설명 - 같은 배열에 합이 있는 배열에 쌍이 없습니다. 따라서 개수는 0입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
arr[]
라고 가정해 봅시다. -
배열의 요소에 따라 정수 값을 반환하는 length() 함수를 사용하여 배열의 길이를 계산합니다.
-
요소 수를 저장할 임시 변수를 가져옵니다.
-
mp
라고 가정해 봅시다. -
i에 대한 루프를 0으로 시작하고 i가 배열 크기보다 작습니다.
-
par
라고 가정해 봅시다. 쌍 유형 변수의 다른 맵을 만듭니다. -
i에 대한 루프를 0으로 시작하고 i가 배열 크기보다 작습니다.
-
루프 내에서 j에서 i+1까지 그리고 j가 배열 크기보다 작은 다른 루프를 시작합니다.
-
루프 내에서 mp[arr[i]+arr[j]]> 0 AND pr[{arr[i], arr[j] }] =0인지 확인한 다음 카운트를 1만큼 증가시킵니다.
-
par[{ arr[i], arr[j] }] 1씩 증가
-
par[{ arr[j], arr[i] }] 1씩 증가
-
개수 반환
-
결과를 인쇄하십시오.
예시
#include <iostream>
#include <map>
using namespace std;
// Returns number of pairs in ar[0..n-1] with
// sum equal to 'sum'
int countpairs(int ar[], int n){
// Store counts of all elements in map m
// to find pair (ar[i], sum-ar[i])
// because (ar[i]) + (sum - ar[i]) = sum
map<int, int> mymap;
for (int i = 0; i < n; i++){
mymap[ar[i]]++;
}
// To remove duplicate items we use result map
map<pair<int, int>, int> p;
int result = 0;
// Considering all pairs
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// If sum of current pair exists
if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] ==0){
result++;
}
// Inserting the current pair both ways to avoid
// duplicates.
p[{ ar[i], ar[j] }]++;
p[{ ar[j], ar[i] }]++;
}
}
return result;
}
// main function
int main(){
int ar[] = { 6, 4, 10, 14 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "count is "<<countpairs(ar, n);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
count is 2