C++로 숫자의 자릿수를 3과 8로만 변환하기

이 튜토리얼에서는 주어진 숫자의 모든 자릿수를 3과 8로만 이루어지도록 변환하는 프로그램을 C++로 구현해 보겠습니다.

문제 개요

임의의 숫자가 하나 주어집니다. 우리의 목표는 이 숫자의 각 자릿수를 3 또는 8로 만드는 것입니다. 이때 사용할 수 있는 연산은 두 가지입니다.

• 숫자 전체에 1을 더하거나 빼기
• 특정 자릿수를 원하는 숫자로 직접 변경하기

여기서 구해야 할 값은 모든 자릿수를 3 또는 8로 만들기 위해 필요한 최소 연산 횟수입니다.

접근 방법

가장 효율적인 방법은 간단합니다. 숫자의 각 자릿수를 차례대로 검사하면서, 3이나 8이 아닌 자릿수마다 한 번의 연산으로 해당 자릿수를 변경하면 됩니다. 즉, 3 또는 8이 아닌 자릿수의 개수가 곧 최소 연산 횟수가 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 최소 연산 횟수 계산
int cal_min(long long int num){
    // 나머지와 연산 횟수 계산
    int rem;
    int count = 0;
    while (num) {
        rem = num % 10;
        if (!(rem == 3 || rem == 8))
        count++;
        num /= 10;
    }
    return count;
}
int main(){
    long long int num = 2341974;
    cout << "Minimum Operations: " << cal_min(num);
    return 0;
}

출력 결과

Minimum Operations: 6

동작 원리

위 코드의 동작 과정을 살펴보겠습니다.

1. num % 10으로 숫자의 마지막 자릿수(일의 자리)를 추출합니다.
2. 추출한 자릿수가 3 또는 8이 아니라면 연산 횟수(count)를 1 증가시킵니다.
3. num /= 10으로 마지막 자릿수를 제거한 뒤, 숫자가 0이 될 때까지 위 과정을 반복합니다.

예제 입력인 2341974의 경우, 자릿수 2, 4, 1, 9, 7, 4는 3이나 8이 아니므로 각각 한 번씩 변경해야 합니다. 반면 3은 이미 조건을 만족하므로 그대로 둡니다. 따라서 총 6번의 연산이 필요하며, 이것이 곧 최소 연산 횟수입니다.

시간 복잡도

이 알고리즘은 숫자의 자릿수만큼만 반복하므로 시간 복잡도는 O(d)입니다(d는 자릿수). 매우 큰 숫자라도 long long int 범위 내에서 빠르게 처리할 수 있습니다.