n개의 양의 정수로 이루어진 배열이 주어졌을 때, arr[x]와 arr[y]의 합이 짝수 또는 홀수가 되는 순서쌍 (arr[x], arr[y])의 개수를 구하는 것이 목표입니다. 이때 (arr[i], arr[j])와 (arr[j], arr[i])는 순서가 다르므로 서로 다른 순서쌍으로 계산합니다.
풀이 방법은 간단합니다. 두 개의 for 루프를 사용해 배열을 순회하면서 각 순서쌍의 합을 구하고, 합이 짝수이면 짝수 합 카운트를 2씩 증가시키고, 홀수이면 홀수 합 카운트를 2씩 증가시킵니다. 2씩 증가시키는 이유는 (a, b)와 (b, a)를 별개의 순서쌍으로 세기 때문입니다.
예시를 통해 자세히 살펴보겠습니다.
예제 1
입력 − Arr[]= { 1,1,2,3 }, N=4
출력 − 짝수 합 순서쌍 개수: 6 / 홀수 합 순서쌍 개수: 6
설명 − 유효한 홀수 합 순서쌍은 다음과 같습니다.
Arr[0] & Arr[1] → (1,1) / Arr[1] & Arr[0] → (1,1) → count=2
Arr[0] & Arr[3] → (1,3) / Arr[3] & Arr[0] → (3,1) → count=2
Arr[1] & Arr[3] → (1,3) / Arr[3] & Arr[1] → (3,1) → count=2
합계 = 6
유효한 짝수 합 순서쌍은 다음과 같습니다.
Arr[0] & Arr[2] → (1,2) / Arr[2] & Arr[0] → (2,1) → count=2
Arr[1] & Arr[2] → (1,2) / Arr[2] & Arr[1] → (2,1) → count=2
Arr[2] & Arr[3] → (2,3) / Arr[3] & Arr[2] → (3,2) → count=2
합계 = 6
예제 2
입력 − Arr[]= { 2,2,2 }, N=3
출력 − 짝수 합 순서쌍 개수: 6 / 홀수 합 순서쌍 개수: 0
설명 − 유효한 짝수 합 순서쌍은 다음과 같습니다.
Arr[0] & Arr[1] → (2,2) / Arr[1] & Arr[0] → (2,2) → count=2
Arr[1] & Arr[2] → (2,2) / Arr[2] & Arr[1] → (2,2) → count=2
Arr[2] & Arr[3] → (2,2) / Arr[3] & Arr[2] → (2,2) → count=2
합계 = 6
모든 원소가 짝수이므로 홀수 합을 가지는 순서쌍은 존재하지 않습니다.
알고리즘 접근 방식
- 임의의 숫자로 초기화된 정수 배열 arr[]를 준비합니다.
- 배열의 길이를 저장할 변수 n을 선언합니다.
- 함수 countPairs(int arr[], int n)는 배열과 그 길이를 입력으로 받아 짝수 합과 홀수 합을 가지는 순서쌍의 개수를 출력합니다.
- 두 개의 for 루프를 사용해 순서쌍을 구성하는 각 원소에 대해 배열을 순회합니다.
- 외부 루프는 0 ≤ i < n-1, 내부 루프는 i < j < n 범위로 실행합니다.
- arr[i]+arr[j] % 2 == 0 인지 검사합니다. 조건이 참이면 (arr[i], arr[j])와 (arr[j], arr[i])가 두 개의 순서쌍이므로 짝수 합 카운트(count1)를 2씩 증가시킵니다.
- 조건이 거짓이면 홀수 합 카운트(count2)를 2씩 증가시킵니다.
- 모든 루프가 종료되면 count1에는 짝수 합 순서쌍의 총 개수가, count2에는 홀수 합 순서쌍의 총 개수가 저장됩니다.
- count1과 count2를 결과로 출력합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void countPairs(int arr[], int n){
int count1=0; // 짝수 합 순서쌍
int count2=0; // 홀수 합 순서쌍
int sum=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
sum=arr[i]+arr[j];
if(sum%2==0) // 합이 짝수인 경우
{ count1+=2; } // (a,b)와 (b,a)를 두 개의 순서쌍으로 계산
else
{ count2+=2; }
}
}
cout<<"Even Sum pairs: "<<count1;
cout<<endl<<"Odd Sum pairs: "<<count2;
}
int main(){
int arr[] = { 1,2,3,2 };
int n = sizeof(arr) / sizeof(int);
countPairs(arr, n);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Even Sum pairs: 4
Odd Sum pairs: 8
참고: 수학적 접근으로 최적화하기
위 방법의 시간 복잡도는 O(n²)입니다. 하지만 덧셈의 성질을 활용하면 O(n)으로 최적화할 수 있습니다. 짝수+짝수=짝수, 홀수+홀수=짝수, 짝수+홀수=홀수이기 때문에, 배열을 한 번만 순회하여 짝수 원소의 개수(evenCount)와 홀수 원소의 개수(oddCount)를 센 뒤 다음 공식을 적용하면 됩니다.
- 짝수 합 순서쌍 수 = evenCount × (evenCount−1) + oddCount × (oddCount−1)
- 홀수 합 순서쌍 수 = evenCount × oddCount × 2
배열의 크기가 클 경우 이 방법을 사용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.