C++에서 문자열로 표현된 두 수 곱하기

두 개의 수가 문자열 형태로 주어져 있을 때, 이 두 수를 곱한 결과 역시 문자열 형태로 반환해야 합니다. 예를 들어 입력이 "26"과 "12"라면 결과는 "312"가 되어야 합니다.

이런 문제가 필요한 이유는 숫자가 매우 커서 int나 long long 같은 기본 정수 자료형에 담을 수 없는 경우에도 곱셈을 수행할 수 있어야 하기 때문입니다. 학교에서 배운 세로셈법(일반적인 손곱셈)의 원리를 그대로 코드로 옮기면 해결할 수 있습니다.

해결 접근 방식

• 두 개의 문자열 num1과 num2를 인자로 받습니다.
• 곱셈 결과의 길이는 최대 n + m(n, m은 각 문자열의 길이)이므로, 길이가 n + m인 문자열 ans를 '0'으로 초기화하여 준비합니다.
• 가장 뒤쪽 자리부터 시작해 각 자릿수 쌍 (i, j)에 대해 다음을 반복합니다.
  • p := (num1[i]의 자릿값) × (num2[j]의 자릿값) + ans[i + j + 1]의 현재 값
  • ans[i + j + 1] := p % 10 → 일의 자리 값을 해당 위치에 저장
  • ans[i + j] += p / 10 → 올림수(carry)를 바로 앞 자리에 더함
• 연산이 모두 끝나면 맨 앞의 불필요한 '0'들을 건너뛰고 나머지 부분을 잘라내어 반환합니다.
• 결과가 전부 '0'이라면 "0"을 반환합니다.

예시(C++)

다음 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string multiply(string num1, string num2);
};
string Solution::multiply(string nums1, string nums2) {
    int n = nums1.size();
    int m = nums2.size();
    string ans(n + m, '0');
    for(int i = n - 1; i>=0; i--){
        for(int j = m - 1; j >= 0; j--){
            int p = (nums1[i] - '0') * (nums2[j] - '0') + (ans[i + j + 1] - '0');
            ans[i+j+1] = p % 10 + '0';
            ans[i+j] += p / 10 ;
        }
    }
    for(int i = 0; i < m + n; i++){
        if(ans[i] !='0')return ans.substr(i);
    }
    return "0";
}
main(){
    Solution ob;
    cout << ob.multiply("28", "25");
}

입력

"26"
"12"

출력

"312"