두 개의 숫자가 문자열 형식으로 주어졌을 때, 이 두 숫자를 곱하는 문제입니다. 이 문제를 해결하는 핵심 아이디어는 이전 자릿수의 곱셈 결과와 올림수(carry)를 계속 유지하는 것입니다. 이전 단계에서 계산한 곱셈 결과와 올림수를 활용하면 다음 자릿수들의 곱셈을 효율적으로 처리할 수 있습니다.
간단한 예시를 통해 살펴보겠습니다.
입력
15 2
출력
30
알고리즘
두 숫자를 문자열 형태로 초기화합니다.
첫 번째 숫자 길이 + 두 번째 숫자 길이만큼의 결과 문자열을 초기화합니다.
첫 번째 숫자를 끝자리부터 시작하여 반복합니다.
두 번째 숫자도 끝자리부터 시작하여 반복합니다.
두 자릿수를 곱하고, 해당 위치에 저장되어 있던 이전 결과값을 더합니다.
해당 위치의 값을 새로운 결과로 갱신합니다.
올림수는 결과 문자열의 바로 앞 인덱스에 저장합니다.
결과 문자열의 모든 문자에 '0' 문자를 더하여 char 값을 실제 숫자로 변환합니다.
앞자리의 불필요한 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;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1938