C++로 숫자 0 만들기: 최소 연산 횟수 구하기

문제 개요

n자리로 이루어진 숫자 문자열 S가 있다고 가정해 보겠습니다. S는 디지털 시계를 나타내며, 문자열 전체는 0부터 10ⁿ − 1 사이의 정수를 표시합니다. 자릿수가 모자랄 경우 앞자리는 0으로 채워져 표시됩니다. 사용할 수 있는 연산은 다음 두 가지입니다.

• 시계에 표시된 숫자를 1만큼 감소시키기
• 두 자리의 숫자를 서로 교환하기

목표는 최소한의 연산으로 시계가 0을 표시하도록 만드는 것이며, 이때 필요한 연산 횟수를 계산해야 합니다.

예를 들어 입력이 S = "1000"이라면 출력은 2입니다. 첫 번째 자리의 1과 마지막 자리의 0을 교환하여 "0001"로 만든 뒤, 숫자를 1 감소시켜 "0000"을 얻을 수 있기 때문입니다.

풀이 접근

이 문제는 다음 단계를 따라 해결할 수 있습니다.

n := S의 길이
x := S[n - 1] 위치의 숫자 값
i := 0부터 n - 2까지 1씩 증가시키며 반복:
    만약 S[i]가 '0'이 아니라면:
        x := x + (S[i] 위치의 숫자 값) + 1
x 반환

핵심 아이디어는 다음과 같습니다. 마지막 자릿수는 그 자리에 그대로 두고 값만큼 감소 연산을 적용해 0으로 만들면 됩니다. 반면 나머지 자리에 있는 0이 아닌 숫자는 한 번의 교환(swap)으로 옮긴 뒤 값만큼 감소시켜야 하므로, 각 숫자마다 '값 + 1'씩 비용이 추가됩니다. 0인 자리는 별도의 연산이 필요하지 않습니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

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

int solve(string S) {
    int n = S.size();
    int x = S[n - 1] - '0';
    for (int i = 0; i <= n - 2; i++)
        if (S[i] != '0')
            x = x + S[i] + 1 - '0';
    return x;
}

int main() {
    string S = "1000";
    cout << solve(S) << endl;
}

입력 및 출력 결과

입력:

"1000"

출력:

2

복잡도 분석

문자열의 각 자리를 한 번씩만 확인하면 되므로 시간 복잡도는 O(n)입니다. 또한 추가적인 저장 공간 없이 상수 크기의 변수만 사용하므로 공간 복잡도는 O(1)입니다.