C++ 배열 요소 곱셈 결과의 마지막 k자리 숫자 구하기

문제 이해하기

n개의 요소로 이루어진 배열 A와 숫자 k가 주어졌을 때, 배열 내 모든 요소를 곱한 값의 마지막 k자리 숫자를 찾아야 합니다.

예를 들어 A = [15, 22, 13, 19, 17]인 경우, 전체 곱은 15 × 22 × 13 × 19 × 17 = 1385670이며, 마지막 k = 3자리는 670입니다.

접근 방법: 모듈로(Modulo) 연산 활용

배열의 크기가 커지면 곱셈 결과도 기하급수적으로 증가하여 int나 long long 같은 기본 정수 자료형의 범위를 쉽게 초과합니다. 따라서 전체 곱을 직접 계산하는 것은 비효율적이며 위험합니다.

여기서 나머지 연산의 성질을 활용할 수 있습니다. 모든 곱셈을 10^k로 나눈 나머지 값에 대해 수행하면, 결과값은 항상 10^k 미만으로 유지되므로 오버플로우 없이 마지막 k자리를 안전하게 구할 수 있습니다.

핵심 원리는 다음과 같습니다. (a × b) % m = ((a % m) × (b % m)) % m

C++ 구현 코드

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

int displayLastKNumbers(int array[], int n, int k) {
    int mod = (int)pow(10, k);
    int mul = array[0] % mod;
    for (int i = 1; i < n; i++) {
        array[i] = array[i] % mod;
        mul = (array[i] * mul) % mod;
    }
    return mul;
}

int main() {
    int a[] = {15, 22, 13, 19, 17};
    int k = 3;
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Last K digits are: " << displayLastKNumbers(a, n, k);
}

실행 결과

Last K digits are: 670

코드 동작 설명

먼저 pow(10, k)를 이용해 10^k 값을 계산하여 mod 변수에 저장합니다. k = 3일 경우 mod는 1000이 됩니다. 그다음 첫 번째 배열 요소를 mod로 나눈 나머지로 초기화하고, 두 번째 요소부터 마지막 요소까지 반복하면서 각 요소를 mod로 나눈 나머지를 현재 곱(mul)과 곱한 뒤 다시 mod를 적용합니다. 반복이 끝나면 mul에는 마지막 k자리 숫자만 남게 됩니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.

마무리

모듈로 연산을 활용하면 아주 큰 곱셈 결과도 오버플로우 걱정 없이 마지막 k자리만 효율적으로 추출할 수 있습니다. 다만 k가 클 경우 10^k 자체가 int 범위를 초과할 수 있으므로, 필요하다면 long long 타입 사용을 고려하는 것이 좋습니다.