C++에서 문자열 변환 없이 숫자의 모든 부분 문자열 출력하기

문제 소개

이 문제에서는 하나의 정수 n이 주어지며, 해당 숫자로 만들 수 있는 모든 부분 문자열(연속된 자릿수 조합)을 출력해야 합니다. 단, 정수를 문자열이나 배열로 변환하는 것은 허용되지 않습니다. 즉, 오직 수학적 연산만으로 문제를 해결해야 한다는 조건이 있습니다.

예시를 통해 문제를 더 잘 이해해 보겠습니다.

입력: number = 5678
출력: 5, 56, 567, 5678, 6, 67, 678, 7, 78, 8

이 문제를 해결하려면 수학적 논리를 적용해야 합니다. 핵심 아이디어는 가장 큰 자릿수(최상위 자릿수)부터 먼저 출력한 뒤, 이후 자릿수를 하나씩 붙여 가며 차례대로 출력하는 것입니다.

알고리즘

1단계: 숫자의 자릿수를 기준으로 10의 거듭제곱 값을 구합니다.
2단계: 숫자를 거듭제곱 값으로 나눈 몫을 출력하고, 거듭제곱 값을 10으로 나누어 가며 0이 될 때까지 반복합니다.
3단계: 숫자의 최상위 자릿수(MSB)를 제거하고, 남은 숫자로 2단계를 다시 수행합니다.
4단계: 숫자가 0이 될 때까지 위 과정을 반복합니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;
void printSubNumbers(int n);
int main(){
    int n = 6789;
    cout<<"The number is "<<n<<" and the substring of number are :\n";
    printSubNumbers(n);
    return 0;
}
void printSubNumbers(int n){
    int s = log10(n);
    int d = (int)(pow(10, s) + 0.5);
    int k = d;
    while (n) {
        while (d) {
            cout<<(n / d)<<" ";
            d = d / 10;
        }
        n = n % k;
        k = k / 10;
        d = k;
    }
}

동작 원리 설명

코드의 핵심 로직을 단계별로 살펴보겠습니다.

log10(n)으로 숫자의 자릿수를 구하고, pow(10, s)를 통해 자릿수에 맞는 10의 거듭제곱 값을 계산합니다. 예를 들어 6789의 경우 d = 1000이 됩니다. 여기서 + 0.5는 부동소수점 오차를 보정하기 위한 장치입니다.
내부 while 루프에서는 n / d를 통해 앞자리부터 잘라낸 값을 출력합니다. 6789 → 6, 67, 678, 6789 순서로 출력됩니다.
외부 루프에서는 n % k로 최상위 자릿수를 제거합니다. 6789 % 1000 = 789가 되어, 이후 7, 78, 789가 출력됩니다.
이 과정이 숫자가 0이 될 때까지 반복되면 모든 부분 문자열이 완성됩니다.

출력 결과

숫자가 6789일 때, 만들 수 있는 부분 문자열은 다음과 같습니다.

6 67 678 6789 7 78 789 8 89 9

마무리

이 방식은 문자열 변환 없이 나눗셈과 나머지 연산만으로 숫자의 모든 부분 문자열을 생성할 수 있는 효율적인 접근 방법입니다. 자릿수가 d인 숫자의 부분 문자열 개수는 d×(d+1)/2개이므로, 전체 시간 복잡도는 O(d²)입니다. 입력 숫자의 자릿수가 길어질수록 출력량도 함께 늘어난다는 점을 참고하시기 바랍니다.