[leetcode #43] Multiply Strings

Problem

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.

Idea

String으로 주어진 두 수의 곱셈을 구하라는 문제다.

곱셈의 원리를 그대로 적용하면 쉽게 풀 수 있다. 다만 String을 char로 변환하고 거기서 '0'을 뺀 값으로 연산을 한 뒤 다시 char로 돌리고 String을 만들어야 하는게 아주 귀찮을 뿐이다.

우선 input 중 하나라도 0이면 0을 곧바로 리턴하도록 했다.

이후에는 char에 '0'을 빼서 곱한 뒤, 올림수와 나머지를 구분해 결과값에 저장하게 했다. 결과값은 char array로 연산이 끝난 뒤, 100이 넘는 수도 있고 10이 넘는 수도 있다. 각각의 수를 한 자리로 표현해야 하므로 10이 넘는 수는 100의 자리를 빼서 두 번째 앞 char로, 10의 자리를 빼서 바로 앞 char에 더한다. 이 과정을 끝내면 char array의 각 원소는 한 자리 수만 남게 된다.

마지막으로 각 char 값에 '0'을 더한 뒤 StringBuilder에 append시켜 String을 리턴하면 된다.

Solution

class Solution {
    public String multiply(String num1, String num2) {
        char first = 0;
        char second = 0;
        char multiplication = 0;
        char round = 0;
        char remainder = 0;
        char surplus = 0;
        int resLength = num1.length() + num2.length();
        char[] res = new char[resLength];

        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        for (int i=num2.length()-1; i >= 0; i--) {
            for (int j=num1.length()-1; j >= 0; j--) {
                first = (char) (num1.charAt(j) - '0');
                second = (char) (num2.charAt(i) - '0');
                multiplication = (char) (first * second);
                round = (char) (multiplication / 10);
                remainder = (char) (multiplication % 10);
                res[i+j+1] += remainder;
                res[i+j] += round;
            }
        }

        for (int i=res.length-1; i >= 0 ; i--) {
            if (res[i] / 100 != 0) {
                res[i-2] += res[i] / 100;
                res[i] %= 100;
            }

            if (res[i] / 10 != 0) {
                res[i-1] += res[i] / 10;
                res[i] %= 10;
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        int startingIndex = 0;
        if (res[0] == 0) {
            startingIndex = 1;
        }
        for (int i=startingIndex; i < res.length; i++) {
            stringBuilder.append((char) (res[i] + '0'));
        }

        return stringBuilder.toString();
    }
}

결과가 좋구만!

Reference

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