정수형 요소로 이루어진 두 개의 배열 arr_1[]과 arr_2[]가 주어졌을 때, 각 배열에서 요소를 하나씩 선택하여 쌍(pair)을 만들고, 그 쌍의 합이 짝수인지 판별한 뒤 조건을 만족하는 쌍의 총 개수를 구하는 것이 이 글의 목표입니다.
예제
예제 1
입력
int arr_1[] = {2, 3, 7, 1, 4};
int arr_2[] = {2, 4, 1, 3};
출력
합이 짝수인 쌍의 개수: 10
설명
두 배열로 만들 수 있는 모든 쌍과 그 합은 다음과 같습니다.
(2, 2) = 4 → 짝수 (유효) (2, 4) = 6 → 짝수 (유효) (2, 1) = 3 → 홀수 (무효) (2, 3) = 5 → 홀수 (무효) (3, 2) = 5 → 홀수 (무효) (3, 4) = 7 → 홀수 (무효) (3, 1) = 4 → 짝수 (유효) (3, 3) = 6 → 짝수 (유효) (7, 2) = 9 → 홀수 (무효) (7, 4) = 11 → 홀수 (무효) (7, 1) = 8 → 짝수 (유효) (7, 3) = 10 → 짝수 (유효) (1, 2) = 3 → 홀수 (무효) (1, 4) = 5 → 홀수 (무효) (1, 1) = 2 → 짝수 (유효) (1, 3) = 4 → 짝수 (유효) (4, 2) = 6 → 짝수 (유효) (4, 4) = 8 → 짝수 (유효) (4, 1) = 5 → 홀수 (무효) (4, 3) = 7 → 홀수 (무효)
위 목록에서 합이 짝수인 유효한 쌍은 총 10개입니다.
예제 2
입력
int arr_1[] = {3, 1, 2};
int arr_2[] = {2, 4};
출력
합이 짝수인 쌍의 개수: 2
설명
만들 수 있는 쌍은 (3, 2) = 5, (3, 4) = 7, (1, 2) = 3, (1, 4) = 5, (2, 2) = 4, (2, 4) = 6으로, 이 중 합이 짝수인 쌍은 (2, 2)와 (2, 4) 두 개뿐입니다.
접근 방법
- 정수형 요소로 이루어진 두 배열을 입력받고, 각 배열의 크기를 계산한 뒤 추가 처리를 위해 함수에 전달합니다.
- 짝수 합을 가지는 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
- i를 0부터 첫 번째 배열의 크기까지 반복하는 FOR 루프를 시작합니다.
- 루프 내부에서 j를 0부터 두 번째 배열의 크기까지 반복하는 FOR 루프를 시작합니다.
- arr_1[i]와 arr_2[j]의 합을 정수 변수 sum에 저장합니다.
- sum % 2 == 0인지, 즉 합이 짝수인지 검사하고 참이라면 count를 1 증가시킵니다.
- 모든 반복이 끝나면 count를 반환합니다.
- 결과를 출력합니다.
이 방법의 시간 복잡도는 두 배열의 크기를 각각 N, M이라 할 때 O(N × M)입니다. 여기서 눈여겨볼 점은 짝수끼리 더하거나 홀수끼리 더할 때만 합이 짝수가 된다는 사실입니다. 따라서 각 배열에서 짝수와 홀수의 개수만 미리 세어 두면 (짝수₁ × 짝수₂) + (홀수₁ × 홀수₂) 공식을 통해 O(N + M) 만에 답을 구할 수도 있습니다.
예제 코드
#include <iostream>
using namespace std;
int even_pair(int arr_1[], int size_arr1, int arr_2[], int size_arr2){
int count = 0;
for(int i = 0; i < size_arr1; i++){
for(int j = 0; j < size_arr2; j++){
int sum = arr_1[i] + arr_2[j];
if(sum % 2 == 0){
count++;
}
}
}
return count;
}
int main(){
int arr_1[] = {2, 3, 7, 1, 4};
int arr_2[] = {2, 4, 1, 3};
int size_arr1 = sizeof(arr_1) / sizeof(arr_1[0]);
int size_arr2 = sizeof(arr_2) / sizeof(arr_2[0]);
cout << "합이 짝수인 쌍의 개수: " << even_pair(arr_1, size_arr1, arr_2, size_arr2);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
합이 짝수인 쌍의 개수: 10