C++로 주어진 숫자에서 가장 작은 자릿수 찾는 프로그램

음이 아닌 정수가 주어졌을 때, 해당 숫자에서 가장 작은 자릿수를 찾는 것이 이번 문제의 목표입니다.

문제 예시

입력:

N = 154870

출력:

설명: 주어진 숫자 '154870'에서 가장 작은 자릿수는 '0'입니다.

문제 해결 접근 방법

이 문제를 푸는 가장 간단한 방법은 나머지 연산(remainder)을 활용해 숫자의 마지막 자릿수부터 하나씩 추출하는 것입니다. 숫자를 순회하면서 추출한 자릿수가 현재까지의 최솟값보다 작으면 최솟값을 갱신하고, 마지막에 결과를 반환하면 됩니다.

알고리즘 단계

숫자 n을 입력으로 받습니다.
정수형 함수 smallest_digit(int n)이 'n'을 입력받아 해당 숫자에서 가장 작은 자릿수를 반환합니다.
먼저 min 변수를 주어진 숫자의 마지막 자릿수(n % 10)로 초기화합니다.
n /= 10으로 마지막 자릿수를 제거하고, 뒤에서 두 번째 자릿수부터 순회를 시작합니다.
반복문 안에서 추출한 자릿수(n % 10)가 현재 최솟값보다 작으면 min을 갱신합니다.
n이 0이 될 때까지 반복한 후, 최종적으로 가장 작은 자릿수를 반환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int smallest_digit(int n) {
    int min = n % 10; //마지막 자릿수가 가장 작다고 가정
    n /= 10; //뒤에서 두 번째 자릿수부터 시작
    while (n != 0) {
        if (min > n % 10)
            min = n % 10;
        n /= 10;
    }
    return min;
}
int main() {
    int n = 154870;
    cout << smallest_digit(n);
    return 0;
}

실행 결과

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

설명: 주어진 숫자 '154870'에서 가장 작은 자릿수는 '0'입니다.

시간 복잡도 분석

이 알고리즘은 숫자의 각 자릿수를 한 번씩만 확인하므로 시간 복잡도는 O(log₁₀ N)입니다. 여기서 N은 입력 숫자의 크기를 의미합니다. 공간 복잡도는 추가 메모리를 거의 사용하지 않으므로 O(1)입니다.