두 개의 숫자가 문자열 형태로 주어졌다고 가정해 봅시다. 이 두 수를 곱한 뒤, 그 결과 역시 문자열 형태로 반환해야 합니다. 예를 들어 "28"과 "25"가 입력으로 주어지면 결과는 "700"이 됩니다.
이 문제가 중요한 이유는 숫자가 매우 커서 int나 long long 같은 기본 정수 자료형의 표현 범위를 초과하는 경우에도 정확한 곱셈 결과를 얻을 수 있기 때문입니다. 초대형 정수(bignum) 연산을 직접 구현할 때 활용되는 대표적인 기법입니다.
알고리즘 접근 방법
핵심 아이디어는 손으로 곱셈을 계산하는 과정을 그대로 코드로 옮기는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- 결과 버퍼 준비: 길이가 n인 수와 길이가 m인 수를 곱하면 결과는 최대 n+m자리가 됩니다. 따라서 길이 n+m의 문자열을 모두 '0'으로 초기화하여 생성합니다.
- 자릿수별 곱셈: 두 문자열의 가장 오른쪽 자릿수(일의 자리)부터 시작해 왼쪽으로 이동하며 이중 반복문을 수행합니다.
- 부분합 계산: nums1[i]와 nums2[j]의 자릿값을 곱한 뒤, 이미 저장되어 있는 결과값(ans[i+j+1])을 함께 더해 올림수까지 반영합니다.
- 결과 저장 및 올림 처리: 계산된 값 p의 1의 자리(p % 10)는 ans[i+j+1]에 기록하고, 올림수(p / 10)는 바로 왼쪽 자리인 ans[i+j]에 더합니다.
- 선행 0 제거: 모든 곱셈이 끝나면 문자열 앞쪽의 불필요한 '0'을 건너뛰고 유효한 숫자 부분만 잘라내어 반환합니다. 만약 전체가 0이라면 "0"을 그대로 반환합니다.
이 알고리즘의 시간 복잡도는 O(n×m)으로, 두 입력 문자열 길이의 곱에 비례합니다.
예제 코드
다음은 위 알고리즘을 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");
}
입력
"28", "25"
출력
"700"
코드 설명
multiply 함수는 먼저 결과 문자열 ans를 길이 n+m, 모든 문자가 '0'인 상태로 생성합니다. 이후 이중 반복문을 통해 각 자릿수 쌍 (i, j)에 대해 곱셈을 수행하는데, 여기서 중요한 점은 nums1[i]와 nums2[j]를 곱한 결과가 ans의 i+j+1번째 위치에 놓인다는 것입니다. 이는 각 자릿수가 가지는 10의 거듭제곱 가중치 때문입니다.
마지막 반복문에서는 문자열 맨 앞에 남아 있을 수 있는 의미 없는 '0'을 제거합니다. 예를 들어 "00" × "00"처럼 모든 자리가 0인 경우에는 최종적으로 "0"을 반환하도록 처리했습니다.