[Leetcode] 43. Multiply Strings

1. 문제링크

Multiply Strings - LeetCode

string num1, string num2의 곱셈 결과를 stoi 등의 integer 변환 함수를 사용하지 않고 풀어야하는 문제

 

 

 

2. key point - vector에 각 자릿수의 곱셈 결과를 기록한다.

1) vector maximum size :  num1.length() + num2.length();

ex) "999" * "999" = "998001"; (3자리 * 3자리 = 6자리)

 

2) vector의 끝부터 계산해나간다. 이 때 idx의 값은 i + j + 1

i+j+1에서 올림값이 있다면 i+j에 올림값을 더해준다

 

 

 

3. solution

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0")
            return "0";

        vector<int> v(num1.size() + num2.size(), 0);
        for(int i = num1.size()-1; i >= 0; i--){
            for(int j = num2.size()-1; j >=0; j--){
                int idx = i+j+1;
                v[idx] += (num1[i]-'0') * (num2[j]-'0');
                v[idx-1] += v[idx] / 10;
                v[idx] %= 10;
            }
        }
                
        int i = 0;
        while(v[i] == 0)
            i++;        

        string res = "";
        for(int idx = i; i < v.size(); i++){
            res += v[i]+'0';
        }

        return res;
    }
};