[Leetcode] 43. Multiply Strings

문제 : https://leetcode.com/problems/multiply-strings/

---

음이 아닌 정수 num1, num2가 문자열로 주어질 때, num1, num2의 곱을 구하라.

---

index   0 1 2

        1 2 3
    x   4 5 6(v)
    -----------
          1 8
        1 2 
        6


ind     0 1 2
        1 2 3
    x   4 5(v) 6
    -----------
        1 5
      1 0   
      5

ind     0 1 2
        1 2 3
    x   4(v) 5 6
    -----------
      1 2
      8   
    4
    
   
 index 0 1 2 3 4 5
               1 8
             1 2
             6
             1 5
           1 0
           5
           1 2
           8
+.       4
 --------------------
       0 5 5 8 8 8

123 * 456 을 예로 들어보자.

한자리 수 씩 곱하는 경우 최소 한자리 최대 두자리가 나온다. (최대 : 9 * 9 = 81)

각 자리수끼리 곱한 수들을 동일한 자리수들끼리 더해주는 경우 정답이 나오는데 이 때 최대 9까지의 carry 값이 각 자리에 더해질 수 있다. 그렇다 하더라도 최대값은 최대 두자리가 나오므로 (최대 : 81 + 9 = 90) n의 자리 수 x m의 자리 수 곱셈의 결과 문자열은 최대 n + m 이다.

만일 num1의 i 번째 자리수와 num2의 j 번째 자리수를 곱한다고 했을 때, 곱한 값은 위 수식으로 알아봤을 때 정답값의 i + j + 1 번째 인덱스를 기준으로 값이 세팅된다.

int multi = num1[i] * num2[j] + calc[i + j + 1];
calc[i + j + 1] = multi % 10; // 10의 자리 
calc[i + j] += multi / 10; // carry 더하기

따라서, calc 배열을 num1 * num2 의 결과값을 저장한 배열이라 할 때 점화식은 위와 같다.

 

위 점화식에 따라 calc 배열을 모두 구한뒤 앞에서부터 연속되는 0을 모두 제거한뒤 숫자를 문자로 바꾸어 calc 배열을 문자열로 바꾸면 정답이 된다.

 

시간복잡도는 O(NM)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/43.%20Multiply%20Strings.cpp