C++에서 문자열로 표현되는 큰 숫자 곱하기

<시간/>

문자열 형식으로 두 개의 숫자가 제공됩니다. 우리는 그것들을 곱해야 합니다. 문제를 해결하기 위한 아이디어는 이전 자릿수 곱셈 답과 캐리를 유지하는 것입니다. 이전 자릿수 곱셈 답과 캐리를 사용하여 다음 세트 자릿수 곱셈을 얻을 수 있습니다.

예를 들어 보겠습니다.

입력

15
2

출력

알고리즘

문자열의 숫자를 초기화합니다.
number_one_length + number_two_length 길이의 문자열을 초기화합니다.
끝에서 첫 번째 숫자를 반복합니다.
- 끝에서 두 번째 숫자를 반복합니다.
  - 두 자리를 곱하고 해당하는 이전 행의 자리를 더하세요.
  - 이전 행 숫자를 업데이트합니다.
  - 결과 문자열의 이전 인덱스에 캐리를 저장합니다.
0을 추가하여 문자를 숫자로 변환 문자를 결과의 모든 문자로 변환합니다.
선행 0을 무시하여 결과를 반환합니다.

구현

다음은 위의 알고리즘을 C++로 구현한 것입니다.

#include <bits/stdc++.h>
using namespace std;
string multiplyTwoNumbers(string num1, string num2) {
   if (num1 == "0" || num2 == "0") {
      return "0";
   }
   string product(num1.size() + num2.size(), 0);
   for (int i = num1.size() - 1; i >= 0; i--) {
      for (int j = num2.size() - 1; j >= 0; j--) {
            int n = (num1[i] - '0') * (num2[j] - '0') + product[i + j + 1];
            product[i + j + 1] = n % 10;
            product[i + j] += n / 10;
      }
   }
   for (int i = 0; i < product.size(); i++) {
      product[i] += '0';
   }
   if (product[0] == '0') {
      return product.substr(1);
   }
   return product;
}
int main() {
   string num1 = "34";
   string num2 = "57";
   if((num1.at(0) == '-' || num2.at(0) == '-') && (num1.at(0) != '-' || num2.at(0) != '-')) {
      cout << "-";
   }
   if(num1.at(0) == '-') {
      num1 = num1.substr(1);
   }
   if(num2.at(0) == '-') {
      num2 = num2.substr(1);
   }
   cout << multiplyTwoNumbers(num1, num2) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.