C++로 x^1부터 x^n까지 거듭제곱 값의 자릿수 빈도 배열 구성하기

두 개의 정수 x와 n이 주어졌다고 가정해 봅시다. 이때 x^1, x^2, …, x^(n-1), x^n으로 계산되는 모든 값에 등장하는 숫자(0~9)의 등장 횟수를 담은 배열을 구해야 합니다.

예를 들어 x = 15, n = 3이라면, 거듭제곱 값은 차례대로 15, 225, 3375입니다. 이 세 수에 나타난 자릿수를 모두 세면 결과는 다음과 같습니다.

[0, 1, 2, 2, 0, 3, 0, 1, 0, 0]

즉, 숫자 1은 한 번, 2는 두 번, 3은 두 번, 5는 세 번, 7은 한 번 나타나고 나머지 숫자는 등장하지 않습니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 숫자 0부터 9까지의 등장 횟수를 저장할 빈도 카운트 배열을 준비합니다.

• x^1부터 x^n까지 각 거듭제곱 값을 계산한 뒤, 해당 값의 모든 자릿수를 하나씩 확인하며 대응하는 인덱스의 카운트를 1씩 증가시킵니다.

• 완성된 빈도 배열을 출력합니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;

// 숫자 하나하나를 확인하며 빈도 배열의 해당 인덱스를 증가시키는 함수
void digitCount(double val, long arr[]) {
    while ((long)val > 0) {
        long digit = (long)val % 10;   // 마지막 자릿수 추출
        arr[(int)digit]++;             // 해당 숫자의 빈도 증가
        val = (long)val / 10;          // 마지막 자릿수 제거
    }
}

void generateFreqArray(int x, int n) {
    long freq_count[10] = {0};
    for (int i = 1; i <= n; i++) {
        double val = pow((double)x, (double)i); // x^i 계산
        digitCount(val, freq_count);
    }
    cout << "[";
    for (int i = 0; i <= 9; i++) {
        cout << freq_count[i] << " ";
    }
    cout << "\b]";
}

int main() {
    int x = 15, n = 3;
    cout << "The frequency array is: ";
    generateFreqArray(x, n);
}

실행 결과

The frequency array is: [0 1 2 2 0 3 0 1 0 0]

코드 설명

digitCount 함수는 전달받은 값의 자릿수를 뒤에서부터 하나씩 추출합니다. 10으로 나눈 나머지(% 10)를 이용해 마지막 자릿수를 얻고, 해당 숫자 인덱스의 카운트를 증가시킨 후 10으로 나누어 다음 자릿수로 넘어갑니다.

generateFreqArray 함수는 1부터 n까지 반복하면서 pow() 함수로 x의 i제곱을 계산하고, 각 값마다 digitCount를 호출하여 빈도를 누적합니다. 최종적으로 0~9까지의 빈도를 순서대로 출력합니다.

다만 큰 수를 다룰 때 double 타입의 정밀도 한계로 인해 오차가 발생할 수 있으므로, 실무에서는 더 큰 정밀도가 필요한 경우 임의 정밀도 연산 라이브러리를 사용하는 것이 좋습니다.