Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 합이 4로 나누어 떨어지는 배열 쌍의 개수 구하기

문제 이해하기

정수형 요소로 이루어진 배열이 주어졌을 때, 배열에서 두 원소를 골라 쌍(pair)을 만들고, 각 쌍의 합이 4로 나누어 떨어지는지 확인한 뒤, 조건을 만족하는 쌍의 개수를 세는 것이 이 글의 목표입니다.

예시 1

입력 − int arr[] = {4, 1, 2, 0, 2}

출력 − 합이 4로 나누어 떨어지는 쌍의 개수: 2

설명 − 주어진 배열로 만들 수 있는 모든 쌍과 그 합은 다음과 같습니다.

  • (4, 1) = 5 → 나누어 떨어지지 않음
  • (4, 2) = 6 → 나누어 떨어지지 않음
  • (4, 0) = 4 → 나누어 떨어짐 ✓
  • (1, 2) = 3 → 나누어 떨어지지 않음
  • (1, 0) = 1 → 나누어 떨어지지 않음
  • (2, 0) = 2 → 나누어 떨어지지 않음
  • (2, 2) = 4 → 나누어 떨어짐 ✓
  • (0, 2) = 2 → 나누어 떨어지지 않음

따라서 합이 4로 나누어 떨어지는 쌍은 (4, 0)과 (2, 2), 총 2개입니다.

예시 2

입력 − int arr[] = {2, 4, 8, 6, 10}

출력 − 합이 4로 나누어 떨어지는 쌍의 개수: 4

설명 − 만들 수 있는 쌍을 하나씩 확인해 보면 (2, 4) = 6, (2, 8) = 10, (2, 6) = 8 ✓, (2, 10) = 12 ✓, (4, 8) = 12 ✓, (4, 6) = 10, (4, 10) = 14, (8, 6) = 14, (8, 10) = 18, (6, 10) = 16 ✓ 입니다. 따라서 조건을 만족하는 쌍은 (2, 6), (2, 10), (4, 8), (6, 10), 총 4개입니다.

접근 방식 1: 완전 탐색 (Naive Approach)

가장 직관적인 방법은 가능한 모든 쌍을 하나씩 검사하는 완전 탐색입니다. 단계는 다음과 같습니다.

  • 정수 배열을 입력받아 배열의 크기를 계산한 뒤 함수에 전달합니다.
  • 합이 4로 나누어 떨어지는 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
  • i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
  • 루프 내부에서 j를 i + 1부터 배열 크기까지 반복하는 중첩 FOR 루프를 시작합니다.
  • 각 반복에서 sum = arr[i] + arr[j]를 계산하고, sum % 4 == 0이면 count를 1 증가시킵니다.
  • 모든 쌍을 검사한 후 count를 반환하고 결과를 출력합니다.

접근 방식 2: 나머지 카운팅 (Efficient Approach)

완전 탐색은 시간 복잡도가 O(n²)이므로 배열이 커지면 비효율적입니다. 대신 각 원소를 4로 나눈 나머지를 활용하면 한 번의 순회로 답을 구할 수 있습니다.

  • 정수 배열을 입력받아 배열의 크기를 계산한 뒤 함수에 전달합니다.
  • 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
  • 나머지별 개수를 저장할 크기 4의 배열 check[]를 생성합니다.
  • 배열을 순회하면서 temp = arr[i] % 4를 구하고 ++check[temp]로 해당 카운트를 증가시킵니다.
  • count = check[0] × (check[0] − 1) ÷ 2 → 나머지가 0인 원소끼리의 쌍
  • count += check[2] × (check[2] − 1) ÷ 2 → 나머지가 2인 원소끼리의 쌍
  • count += check[1] × check[3] → 나머지가 1인 원소와 3인 원소의 쌍
  • count를 반환하고 결과를 출력합니다.

핵심 아이디어

두 수의 합이 4로 나누어 떨어지려면 두 수의 나머지 합이 0 또는 4여야 합니다. 즉 가능한 나머지 조합은 (0, 0), (2, 2), (1, 3) 세 가지뿐입니다. 같은 그룹에서 두 개를 고르는 경우의 수는 n × (n − 1) ÷ 2이며, 서로 다른 그룹에서 하나씩 고르는 경우의 수는 두 그룹 크기의 곱입니다. 이 덕분에 배열을 한 번만 순회해도 정답을 얻을 수 있습니다.

예제 코드 (완전 탐색)

#include <iostream>
using namespace std;
int pair_4(int arr[], int size){
    int count = 0;
    for(int i = 0 ;i <size ; i++){
        for(int j = i+1; j<size; j++){
            int sum = arr[i] + arr[j];
            if(sum % 4 == 0){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {4, 1, 2, 0, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_4(arr, size);
    return 0;
}

실행 결과

Count pairs in array whose sum is divisible by 4 are: 2

예제 코드 (나머지 카운팅)

#include <iostream>
using namespace std;
int pair_4(int arr[], int size){
    int temp = 0;
    int count = 0;
    int check[] = {0, 0, 0, 0};
    for (int i = 0; i < size; i++){
        temp = arr[i] % 4;
        ++check[temp];
    }
    count = check[0] * (check[0] - 1) / 2;
    count = count + check[2] * (check[2] - 1) / 2;
    count = count + check[1] * check[3];
    return count;
}
int main(){
    int arr[] = {4, 1, 2, 0, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_4(arr, size);
    return 0;
}

실행 결과

Count pairs in array whose sum is divisible by 4 are: 2

시간 복잡도 비교

접근 방식시간 복잡도공간 복잡도
완전 탐색O(n²)O(1)
나머지 카운팅O(n)O(1)

두 방법 모두 추가 공간은 거의 필요하지 않지만, 원소 개수가 많아질수록 나머지 카운팅 방식이 압도적으로 빠릅니다. 실무에서는 특별한 이유가 없다면 O(n) 방식을 사용하는 것이 좋습니다.