C++로 배열에서 주어진 조건을 만족하는 유효한 쌍 개수 구하기

문제 개요

N개의 요소로 이루어진 배열 arr[]가 주어졌을 때, 특정 조건을 만족하는 모든 유효한 쌍 (Arr[i], Arr[j])의 개수를 구하는 것이 목표입니다.

쌍 (Arr[i], Arr[j])이 유효하려면 다음 세 가지 조건을 모두 만족해야 합니다.

Arr[i] == Arr[j] : 두 요소의 값이 서로 같아야 합니다.
Arr[i] + Arr[j]가 짝수 : 두 요소의 합이 짝수여야 합니다.
i + j < 120 : 두 인덱스의 합이 120보다 작아야 합니다.

참고 – (Arr[i], Arr[j])와 (Arr[j], Arr[i])는 동일한 쌍으로 간주하여 한 번만 계산하며, 유효한 쌍은 반드시 i != j여야 합니다.

예제로 이해하기

예제 1

입력

Arr[] = { 3, 2, 1, 2, 4, 3 }, N = 6

출력

유효한 쌍의 개수: 2

설명

배열에서 값이 같은 요소들의 쌍은 아래 두 가지이며, 두 쌍 모두 합이 짝수이고 인덱스 합이 120 미만이므로 유효합니다.

Arr[0]과 Arr[5] → (3, 3) : 값이 같고, 3+3=6은 짝수, i != j, i+j = 5 < 120
Arr[1]과 Arr[3] → (2, 2) : 값이 같고, 2+2=4는 짝수, i != j, i+j = 4 < 120

예제 2

입력

Arr[] = { 1, 2, 3, 4, 5, 6 }, N = 6

출력

유효한 쌍의 개수: 0

설명

모든 요소가 서로 다르므로 i != j를 만족하는 (a, a) 형태의 쌍이 존재할 수 없습니다. 따라서 유효한 쌍은 0개입니다.

접근 방법

임의의 숫자로 초기화된 정수 배열 Arr[]와 배열의 길이를 저장하는 변수 n을 준비합니다.
countPairs(int arr[], int n) 함수는 배열과 그 길이를 입력받아 조건을 만족하는 유효한 쌍의 개수를 반환합니다.
두 개의 중첩 for 루프를 사용해 가능한 모든 쌍을 검사합니다. 바깥 루프는 0 ≤ i < n-1, 안쪽 루프는 i < j < n 범위로 실행합니다.
안쪽 루프의 시작을 j = i + 1로 설정하면 자기 자신과의 쌍(i == j)이 자동으로 제외되므로, 별도의 i != j 검사가 필요 없습니다.
각 쌍에 대해 합을 계산합니다: sum = arr[i] + arr[j].
sum % 2 == 0(합이 짝수)이고 i + j < 120인지 확인한 뒤, arr[i] == arr[j]이면 count를 1 증가시킵니다.
모든 루프가 종료되면 count에는 유효한 쌍의 총 개수가 저장되며, 이 값을 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n){
    int count = 0;
    for(int i = 0; i < n; i++){
        // j를 i+1부터 시작하면 i != j 검사가 필요 없음
        for(int j = i + 1; j < n; j++)
        {
            int sum = arr[i] + arr[j];
            // 합이 짝수이고 인덱스 합이 120 미만인 경우
            if(sum % 2 == 0 && i + j < 120){
                // 두 요소의 값이 같으면 유효한 쌍
                if(arr[i] == arr[j])
                {
                    count++;
                    cout << endl << " a:" << arr[i] << " b: " << arr[j];
                }
            }
        }
    }
    return count;
}

int main(){
    int arr[] = {1, 2, 3, 2, 4, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << endl << "Valid pairs in array: " << countPairs(arr, n);
    return 0;
}

출력 결과

Valid pairs in array:
 a:1 b: 1
 a:2 b: 2
 a:4 b: 4
3

출력에서 (1, 1), (2, 2), (4, 4) 세 쌍이 모든 조건을 만족하며, 마지막 숫자 3이 유효한 쌍의 총 개수입니다.

복잡도 분석

시간 복잡도: O(n²) – 두 개의 중첩 루프로 가능한 모든 쌍을 검사합니다.
공간 복잡도: O(1) – 추가적인 자료구조 없이 카운터 변수만 사용합니다.

마무리

이 문제는 중첩 루프를 활용한 완전 탐색으로 해결할 수 있습니다. 안쪽 루프를 j = i + 1부터 시작하면 중복 쌍과 자기 자신과의 비교를 자연스럽게 제외할 수 있어 코드가 더 깔끔해집니다. 배열 크기가 매우 큰 경우에는 값의 빈도를 미리 집계하는 해시맵 기반 최적화도 고려해볼 수 있습니다.