C++에서 자릿수 교체를 활용해 두 수의 최대·최소 합 구하기

두 개의 양의 정수 num1과 num2가 주어졌을 때, 각 숫자에 포함된 특정 자릿수를 다른 숫자로 교체한 후 얻을 수 있는 최소 합과 최대 합을 구하는 것이 이 글의 목표입니다.

예를 들어 num1이 434이고 num2가 324라고 가정해 보겠습니다. 자릿수 3을 4로, 4를 3으로 서로 바꿀 수 있다면 최소 합은 333+323=656이 되고, 최대 합은 444+424=864가 됩니다.

그럼 자릿수 3을 4로 바꾸거나 그 반대로 바꾸는 구체적인 예제를 통해 문제를 이해해 보겠습니다.

예제 1

입력

num1=3224 num2=4321

출력

Maximum sum is : 8645
Minimum sum is : 6544

설명: 4가 3보다 크기 때문에 모든 3을 4로 바꾸면 두 수가 더 커집니다.

num1은 4224가 되고, num2는 4421이 되며, 합은 8645입니다.

반대로 3이 4보다 작기 때문에 모든 4를 3으로 바꾸면 두 수가 더 작아집니다.

num1은 3223이 되고, num2는 3321이 되며, 합은 6544입니다.

예제 2

입력

num1=3111 num2=4111

출력

Maximum sum is : 8222
Minimum sum is : 6222

설명: 모든 3을 4로 바꾸면 num1은 4111, num2는 4111이 되어 합은 8222입니다. 반대로 모든 4를 3으로 바꾸면 num1은 3111, num2는 3111이 되어 합은 6222입니다.

문제 해결 접근 방식

위 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

두 숫자는 변수 num1과 num2에 저장되어 있습니다.
calculateSum(int n1, int n2) 함수는 자릿수 교체 후의 최소 합과 최대 합을 계산하는 역할을 담당합니다.
이 함수는 두 숫자 n1과 n2를 매개변수로 받아 결과를 minSum과 maxSum에 저장한 뒤 출력합니다.
먼저 replace(n1, 4, 3)와 replace(n2, 4, 3)를 호출하여 두 숫자의 모든 4를 3으로 바꾼 새로운 값을 저장합니다.
새로운 num1과 num2를 더하여 최소 합을 계산합니다.
같은 방식으로 replace(n1, 3, 4)와 replace(n2, 3, 4)를 호출하여 모든 3을 4로 바꾼 뒤 최대 합을 계산합니다.

replace() 함수의 동작 원리

replace(int x, int digit1, int digit2) 함수는 x에 포함된 모든 digit1을 digit2로 바꾸고 새로운 숫자를 반환합니다.

새로 만들어진 숫자를 저장할 변수 number를 0으로 초기화합니다.
temp는 각 반복마다 10을 곱하는 배율(multiplier) 역할을 합니다.
x를 10으로 나눈 나머지(rem)를 통해 오른쪽부터 한 자리씩 추출합니다.
rem이 digit1과 같으면 digit2로 교체하여 number = number + digit2 * temp를 계산하고, 그렇지 않으면 number = number + rem * temp로 그대로 더합니다.
x를 10으로 나누어 줄이고, 배율은 temp = temp * 10으로 증가시킵니다.
모든 자릿수를 처리한 후 완성된 number를 반환합니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
// digit1을 digit2로 교체하는 함수
int replace(int x, int digit1, int digit2){
    int number = 0;
    int temp = 1;
    while (x > 0){
        int rem = x % 10;
        // 찾고자 하는 자릿수라면 교체
        if (rem == digit1)
            number = number + digit2 * temp;
        else
            number = number + rem * temp;
        temp *= 10;
        x = x / 10;
    }
    return number;
}
void calculateSum(int n1, int n2){
    // 4를 3으로 교체 → 최소 합
    int num1=replace(n1,4,3);
    int num2=replace(n2,4,3);
    int minSum=num1+num2;
    // 3을 4로 교체 → 최대 합
    num1=replace(n1,3,4);
    num2=replace(n2,3,4);
    int maxSum=num1+num2;
    std::cout << "Minimum Sum by digit replacement: " << minSum;
    std::cout << "\nMaximum Sum by digit replacement: " << maxSum;
}
int main(){
    int num1 = 3131, num2 = 4141;
    calculateSum(num1, num2);
    return 0;
}

실행 결과

Minimum Sum by digit replacement: 6262
Maximum Sum by digit replacement: 8282

이처럼 자릿수 교체 로직을 활용하면 주어진 조건에서 만들 수 있는 최소 합과 최대 합을 손쉽게 계산할 수 있습니다. 시간 복잡도는 각 숫자의 자릿수에 비례하므로 O(d)이며, 여기서 d는 숫자의 자릿수입니다.