C++에서 1 더하기·후행 0 제거 연산으로 N에서 만들 수 있는 고유 숫자 개수 구하기

문제 개요

숫자 N이 입력으로 주어졌을 때, N에 아래 두 가지 연산을 반복적으로 적용한 후 그 과정에서 생성되는 고유한 숫자의 개수를 구하는 것이 목표입니다.

연산 1: 현재 숫자에 1을 더합니다.
연산 2: 결과 숫자 끝에 붙은 0(후행 0)이 있다면 모두 제거합니다.

동작 예시: N = 8

연산 1 적용: 8 → 9

연산 2 적용: 9 + 1 = 10 → 1 (10에서 후행 0 제거)

이후에는 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 순서로 진행되며 처음과 동일한 수열이 반복됩니다.

따라서 생성되는 고유한 숫자는 총 9개입니다.

입출력 예제

예제 1

입력:

N = 21

출력:

1을 더하고 후행 0을 제거하여 N에서 생성할 수 있는 고유 숫자의 개수: 18

설명: 생성되는 숫자는 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 4, 5, 6, 7, 8, 9, 1, 2 순서이며, 이후부터는 같은 수열이 반복됩니다. 따라서 고유한 숫자는 총 18개입니다.

예제 2

입력:

N = 38

출력:

1을 더하고 후행 0을 제거하여 N에서 생성할 수 있는 고유 숫자의 개수: 11

설명: 생성되는 숫자는 38, 39, 4, 5, 6, 7, 8, 9, 1, 2, 3 순서이며, 이후부터는 같은 수열이 반복됩니다. 따라서 고유한 숫자는 총 11개입니다.

접근 방법

이 문제는 unordered_set(정렬되지 않은 집합) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

연산을 적용하며 생성되는 모든 숫자를 unordered_set에 삽입합니다.
이미 집합에 존재하는 숫자가 다시 나타나면 수열이 반복되기 시작한 것이므로 탐색을 종료합니다.
최종적으로 집합의 크기(size)가 곧 생성된 고유 숫자의 개수가 됩니다.

알고리즘 단계

숫자 N을 정수형으로 입력받습니다.
생성된 숫자를 저장할 unordered_set<int> 타입의 U_S를 선언합니다.
함수 unique_N(unordered_set<int>& U_S, int N)은 집합과 N을 매개변수로 받아, 집합 안의 모든 숫자가 고유한 동안 새 숫자를 추가합니다.
U_S.count(N)이 1을 반환하면 N이 이미 집합에 존재한다는 뜻입니다. 이는 숫자가 반복되기 시작했다는 의미이므로 함수를 종료합니다.
그렇지 않으면 N을 집합에 삽입한 뒤 연산 1(N을 1 증가)을 적용합니다.
N의 끝에 0이 있는지 확인합니다(즉, 10의 배수인지 검사).
N % 10이 0이라면 N을 10으로 나누어 후행 0을 제거합니다.
갱신된 N을 인자로 하여 함수 unique_N()을 재귀 호출합니다.
함수가 종료된 후 집합 U_S의 크기를 개수(count)로 저장합니다.
결과값 count를 출력합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

void unique_N(unordered_set<int>& U_S, int N){
    if (U_S.count(N)){
        return;
    }
    U_S.insert(N);
    N = N + 1;
    while (N % 10 == 0){
        N = N / 10;
    }
    unique_N(U_S, N);
}

int main(){
    int N = 7;
    unordered_set<int> U_S;
    unique_N(U_S, N);
    int count = U_S.size();
    cout<<"Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: "<<count;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 9

복잡도 분석

각 숫자는 최대 한 번만 집합에 삽입되므로, 생성되는 고유 숫자의 개수를 k라 할 때 시간 복잡도는 O(k)입니다. 공간 복잡도 역시 집합에 저장되는 원소의 수만큼 O(k)입니다.