LeetCode Multiply Strings (JavaScript)

링크 : https://leetcode.com/problems/multiply-strings/

문제 설명

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

---

문제 풀이

문자열로된 num1, num2를 곱한 값을 리턴 -> 일반적인 * 연산으로 할 경우 overflow가 발생하여 값이 제대로 출력되지 않음

방법

1. num1의 길이 + num2의 길이 만큼 배열을 생성 (최대 자릿수)

• ex) 999 / 999 라고 했을 때 최대 자릿수는 6자리임
• 쉽게 생각하면 1000 * 1000 = 1,000,000 (7자리) > 999 * 999 = 998,001(6자리) 이기 때문에 최대 6자리만 가질 수 있음

2. 뒤에서 부터 계산

• 문자열을 숫자로 하는 방법 -> +를 붙이면 됨
• product에 각 숫자를 곱한 값 저장
• 10이상인 값에 대해서 다음 자리에 더해야 하기 때문에 position을 2개 구함
  • p1 : 이전 자리 위치 (10보다 큰 값에 대해서 올림을 하기 위해)
  • p2 : 내가 저장할 위치
• p1자리에 10으로 나눈 몫을 더해줌 -> 다음으로 이전 자리 값을 계산할 때 sum에 해당 위치의 값을 더해서 누적 값 계산하는 방식
• p2자리에 10으로 나눈 나머지를 더해줌

3. 최종 리턴

• 주의할 점은 answer을 join하여 하나의 문자열로 만들고 정수로 바꾸면 overflow가 발생하기 때문에 그냥 문자열 자체로 리턴해야 함
• 또한, 배열은 최대 자릿수 만큼 선언되어있기 때문에 앞에 0으로 되어있을 수 있음
  • [0, 0, 1, 2, 3] -> '123' 으로 해야 함
  • 따라서, 앞에 0을 없애기 위해 index를 조정

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    const answer = Array.from({length: (num1.length + num2.length)}, () => 0);

    for (let i = num1.length - 1; i >= 0; i--) {
        for (let j = num2.length - 1; j >= 0; j--) {
            const product = +num1[i] * +num2[j];

            const p1 = i + j;
            const p2 = i + j + 1;

            const sum = product + answer[p2];

            answer[p1] += Math.floor(sum / 10);

            answer[p2] = sum % 10;
        }
    }

    let index = 0;
    while (index < answer.length - 1 && answer[index] === 0) {
        index++;
    }

    return answer.slice(index).join('');
};

---

결론

문자열로 처리하기위해 각 숫자를 곱한 최대 자리수만큼의 배열을 선언하는 것이 핵심

10을 초과하는 값에 대해 다음 계산을 위해 더해주는 로직도 중요