C++로 10의 거듭제곱(10^K)으로 나누어 떨어지게 만드는 최소 제거 자릿수 구하기

문제 설명

두 양의 정수 N과 K가 주어졌을 때, 숫자 N에서 몇 개의 자릿수를 제거해야 제거 후 남은 수가 10^K(10의 거듭제곱)으로 나누어 떨어지는지, 그 최소 제거 자릿수를 구하는 문제입니다. 만약 어떻게 해도 조건을 만족할 수 없다면 -1을 출력합니다.

예시

N = 10203027, K = 2인 경우를 생각해 보겠습니다. 이때 제거해야 할 자릿수는 3개입니다. 자릿수 3, 2, 7을 차례로 제거하면 숫자는 10200이 되고, 10200은 10² = 100으로 나누어 떨어집니다.

알고리즘 접근 방식

이 문제의 핵심은 간단합니다. 어떤 수가 10^K으로 나누어 떨어지려면 반드시 끝자리에 0이 K개 이상 연속해서 있어야 합니다. 따라서 숫자를 뒤에서부터 탐색하며, 0이 아닌 자릿수는 제거 대상으로 세고, 0을 만날 때마다 아직 확보해야 할 0의 개수(K)를 하나씩 줄여 나가면 됩니다.

숫자의 마지막 자릿수부터 앞쪽으로 한 자릿수씩 탐색합니다. 현재 자릿수가 0이 아니면 카운터 변수(result)를 증가시키고, 0이면 변수 K를 감소시킵니다.
탐색 도중 K가 0이 되면, 그때까지 세어 온 카운터 값을 정답으로 반환합니다.
전체 탐색이 끝난 후에도 K가 0이 아니라면, 지금까지 0을 발견했는지 확인합니다. 0이 하나라도 있었다면 N의 자릿수 - 1을 정답으로 반환하고, 없었다면 다음 단계로 진행합니다.
주어진 숫자에 0이 하나도 포함되어 있지 않다면 -1을 반환합니다.

C++ 구현 코드

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

// 10^K으로 나누어 떨어지도록 제거해야 하는 최소 자릿수를 계산하는 함수
int getBitsToBeRemoved(int n, int k) {
    string s = to_string(n);   // 숫자를 문자열로 변환
    int result = 0;            // 제거해야 할 자릿수 개수
    int zeroFound = 0;         // 0 발견 여부 플래그

    // 끝자리부터 앞자리 방향으로 탐색
    for (int i = s.size() - 1; i >= 0; --i) {
        if (k == 0) {              // 필요한 0을 모두 확보한 경우
            return result;
        }
        if (s[i] == '0') {         // 0을 발견하면
            zeroFound = 1;
            --k;                   // 남은 0의 개수 감소
        } else {                   // 0이 아닌 자릿수는 제거 대상
            ++result;
        }
    }

    if (!k) {                      // K개의 0을 모두 찾은 경우
        return result;
    } else if (zeroFound) {        // 0은 있지만 K개 미만인 경우
        return s.size() - 1;
    }
    return -1;                     // 0이 하나도 없는 경우
}

int main() {
    int n = 10203027;
    int k = 2;
    cout << "최소 제거 자릿수 = " << getBitsToBeRemoved(n, k) << endl;
    return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

최소 제거 자릿수 = 3

시간 복잡도

시간 복잡도는 O(d)입니다. 여기서 d는 숫자 N의 자릿수 개수로, 숫자를 한 번만 순회하면 답을 구할 수 있으므로 매우 효율적인 알고리즘입니다.