C++로 구현하는 3으로 나누어 떨어지는 크기 2·3 그룹 개수 찾기

문제 소개

숫자로 이루어진 배열이 주어졌을 때, 원소의 합이 3으로 나누어 떨어지는 크기 2와 크기 3의 그룹이 각각 몇 개 존재하는지 구해야 합니다. 해결 방법은 간단합니다. 배열에서 두 개씩, 세 개씩 원소를 조합하여 각 그룹의 합을 계산하고, 그 합이 3으로 나누어 떨어지는지 확인하면 됩니다.

먼저 예시를 살펴보겠습니다.

입력

arr = [1, 2, 3, 4]

출력

4

합이 3으로 나누어 떨어지는 조합은 다음과 같이 총 4개입니다.

[1, 2] → 합 = 3
[2, 4] → 합 = 6
[1, 2, 3] → 합 = 6
[2, 3, 4] → 합 = 9

알고리즘

• 배열을 초기화합니다.

• 두 개의 중첩 반복문을 사용해 크기 2인 모든 조합을 만듭니다.

  • 각 그룹의 합을 계산합니다.

  • 합이 3으로 나누어 떨어지면 카운트를 1 증가시킵니다.

• 세 개의 중첩 반복문을 사용해 크기 3인 모든 조합을 만듭니다.

  • 각 그룹의 합을 계산합니다.

  • 합이 3으로 나누어 떨어지면 카운트를 1 증가시킵니다.

• 최종 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int getNumberOfGroupsDivisibleBy3(int arr[], int n) {
    int count = 0;
    // 크기 2인 그룹 검사
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            if (sum % 3 == 0) {
                count += 1;
            }
        }
    }
    // 크기 3인 그룹 검사
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = arr[i] + arr[j] + arr[k];
                if (sum % 3 == 0) {
                    count += 1;
                }
            }
        }
    }
    return count;
}
int main() {
    int arr[] = { 2, 3, 4, 5, 6, 1, 2, 4, 7, 8 };
    int n = 10;
    cout << getNumberOfGroupsDivisibleBy3(arr, n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

57

즉, 주어진 배열에서 합이 3으로 나누어 떨어지는 크기 2 또는 3의 그룹은 총 57개입니다.

시간 복잡도 분석

크기 2인 그룹을 검사하는 데 O(n²), 크기 3인 그룹을 검사하는 데 O(n³)의 시간이 걸리므로, 전체 시간 복잡도는 O(n³)입니다. 공간 복잡도는 추가 배열 없이 카운터 변수만 사용하므로 O(1)입니다. 배열의 크기가 작다면 이 방법으로 충분하지만, 입력이 커질 경우 나머지(0, 1, 2)별 원소 개수를 세어 조합 공식으로 계산하는 최적화 기법을 고려할 수 있습니다.