C++로 GCD 배열에서 원래 숫자 복원하는 방법

개념

어떤 배열 array[]에 다른 배열을 구성하는 요소들의 모든 가능한 쌍에 대한 GCD(최대공약수) 값이 저장되어 있다고 가정해 봅시다. 이때 우리의 과제는 이 GCD 배열을 계산하는 데 사용된 원래 숫자들을 역으로 찾아내는 것입니다.

예를 들어, 원래 배열이 {13, 6}이라면 두 요소로 만들 수 있는 모든 쌍(자기 자신과의 쌍 포함)의 GCD는 다음과 같습니다.

gcd(13, 13) = 13
gcd(13, 6) = 1
gcd(6, 13) = 1
gcd(6, 6) = 6

따라서 입력으로 {13, 1, 1, 6}이 주어지면, 출력으로 원래 숫자인 13과 6을 반환해야 합니다.

입력 예시

array[] = {6, 1, 1, 13}

출력 예시

13 6

추가 예시

입력:

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}

출력:

13 11 8 6 6

접근 방법

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.

먼저 배열을 내림차순으로 정렬합니다.
배열에서 가장 큰 원소는 반드시 원래 숫자 중 하나입니다. 왜냐하면 어떤 수와의 GCD도 그 수 자체보다 클 수 없기 때문입니다. 이 숫자를 결과 배열에 저장하고, 빈도 배열에서 해당 값을 하나 감소시킵니다.
다음으로, 현재 확인 중인 원소와 이미 확정된 각 원래 숫자 사이의 GCD를 계산하고, 그 GCD 값을 빈도 배열에서 제거합니다. 이렇게 하면 이미 처리된 쌍의 GCD가 남은 후보 목록에서 걸리적거리지 않게 됩니다.
위 과정을 배열 전체를 순회할 때까지 반복하면, 빈도가 아직 남아 있는 원소들이 곧 원래 숫자들이 됩니다.

원래 배열의 크기를 n이라 할 때, 모든 쌍의 개수는 n²이므로 원래 배열의 크기는 √n으로 계산할 수 있습니다.

C++ 구현 예제

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// 배열 내용을 출력하는 유틸리티 함수
void printArr(int array[], int n1){
    for (int i = 0; i < n1; i++)
        cout << array[i] << " ";
}

// 필요한 원래 숫자들을 찾는 함수
void findNumbers(int array[], int n1){
    // 배열을 내림차순으로 정렬
    sort(array, array + n1, greater<int>());
    int freq1[array[0] + 1] = { 0 };

    // 각 원소의 빈도수 계산
    for (int i = 0; i < n1; i++)
        freq1[array[i]]++;

    // 결과 배열의 크기
    int size1 = sqrt(n1);
    int brr1[size1] = { 0 }, x1, l1 = 0;

    for (int i = 0; i < n1; i++) {
        if (freq1[array[i]] > 0) {
            // 가장 큰 원소를 결과 배열에 저장
            brr1[l1] = array[i];
            // 해당 원소의 빈도 감소
            freq1[brr1[l1]]--;
            l1++;
            for (int j = 0; j < l1; j++) {
                if (i != j) {
                    // GCD 계산
                    x1 = __gcd(array[i], brr1[j]);
                    // GCD 값만큼 빈도 감소
                    freq1[x1] -= 2;
                }
            }
        }
    }
    printArr(brr1, size1);
}

// 드라이버 코드
int main(){
    /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                      1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */
    int array[] = { 6, 1, 1, 13};
    int n1 = sizeof(array) / sizeof(array[0]);
    findNumbers(array, n1);
    return 0;
}

실행 결과

13 6

동작 원리 정리

이 알고리즘의 핵심은 GCD의 성질을 활용하는 것입니다. 임의의 두 수 a, b에 대해 gcd(a, b) ≤ min(a, b)가 항상 성립하므로, 내림차순으로 정렬된 배열에서 아직 소비되지 않은 가장 큰 값은 반드시 원래 숫자여야 합니다. 새로운 원래 숫자를 확정할 때마다 그 숫자와 기존에 확정된 숫자들 사이의 GCD를 빈도 배열에서 차감함으로써, 실제 쌍에서 유래한 GCD 값들을 정확히 제거해 나갈 수 있습니다.

시간 복잡도는 정렬에 O(n log n), 각 원소마다 기존 확정 숫자들과의 GCD 계산에 O(√n)씩 소요되므로 전체적으로 약 O(n log n + n√n) 수준으로 효율적입니다.