C++로 숫자의 M개 연속 자릿수 최대 합과 곱 구하기

문제 개요

이 문제에서는 하나의 숫자를 나타내는 문자열이 주어집니다. 우리의 목표는 C++을 활용하여 숫자 안에서 M개의 연속된 자릿수를 선택했을 때 얻을 수 있는 최대 합(sum)과 최대 곱(product)을 구하는 프로그램을 작성하는 것입니다.

문제 설명

주어진 숫자에서 길이가 M인 모든 연속 부분 수열을 찾고, 각 부분 수열에 포함된 자릿수들의 합과 곱을 계산한 뒤, 그중 가장 큰 값을 반환합니다.

예시를 통해 문제를 자세히 이해해 보겠습니다.

입력

number = 2379641, M = 4

출력

maxSum = 26
maxProd = 1512

설명

크기가 4인 모든 연속 부분 수열은 2379, 3796, 7964, 9641입니다.
최대 합(maxSum) = 7 + 9 + 6 + 4 = 26
최대 곱(maxProd) = 7 × 9 × 6 × 4 = 1512

풀이 접근 방법

가장 직관적인 해결 방법은 숫자에서 만들 수 있는 길이 M의 모든 연속 부분 수열을 하나씩 살펴보는 것입니다. 각 부분 수열마다 자릿수의 합과 곱을 계산하고, 지금까지 구한 최댓값과 비교하여 더 큰 값으로 갱신합니다. 모든 경우를 확인한 뒤 최종적으로 남은 값이 바로 최대 합과 최대 곱입니다.

예제 코드

아래 프로그램은 위에서 설명한 풀이 과정을 그대로 구현한 예제입니다.

#include <iostream>
using namespace std;

// 두 값 중 더 큰 값을 반환하는 헬퍼 함수
int findMaxVal(int x, int y){
    return (x > y) ? x : y;
}

// M개의 연속 자릿수에 대한 최대 합과 곱을 계산하는 함수
void calcMaxProductAndSum(string number, int M){
    int N = number.length();
    int maxProd = -1, maxSum = -1;

    // 마지막 윈도우까지 포함하기 위해 i <= N - M 조건 사용
    for (int i = 0; i <= N - M; i++){
        int product = 1, sum = 0;
        for (int j = i; j < M + i; j++){
            product *= (number[j] - '0');
            sum += (number[j] - '0');
        }
        maxProd = findMaxVal(maxProd, product);
        maxSum = findMaxVal(maxSum, sum);
    }

    cout << "숫자 " << number << "에서 연속된 " << M << "개 자릿수의 최대 곱: " << maxProd << endl;
    cout << "숫자 " << number << "에서 연속된 " << M << "개 자릿수의 최대 합: " << maxSum;
}

int main() {
    string str = "2379641";
    int m = 4;
    calcMaxProductAndSum(str, m);
    return 0;
}

출력 결과

숫자 2379641에서 연속된 4개 자릿수의 최대 곱: 1512
숫자 2379641에서 연속된 4개 자릿수의 최대 합: 26

시간 복잡도 분석

위 풀이는 시작 위치마다 M개의 자릿수를 다시 계산하므로 시간 복잡도는 O(N×M)입니다. 여기서 N은 숫자의 전체 길이입니다. 슬라이딩 윈도우 기법을 적용하면 윈도우가 한 칸 이동할 때 빠져나가는 자릿수와 새로 들어오는 자릿수만 반영하면 되므로, 시간 복잡도를 O(N)까지 줄일 수 있습니다.

마무리

이처럼 문자열로 표현된 숫자에서 각 문자에 '0'을 빼주면 손쉽게 정수형 자릿값으로 변환할 수 있으며, 이를 활용해 연속 구간의 합과 곱을 효율적으로 계산할 수 있습니다. 입력 크기가 커질 가능성이 있다면 슬라이딩 윈도우 최적화를 함께 고려하는 것이 좋습니다.