[leetcode 75] 43. Multiply Strings

문제해석

음수가 아닌 num1과 num2가 문자열로 주어졌을 때 두 수의 곱을 문자열로 표기하기

BigInteger 라이브러리나 입력값을 바로 정수로 전화하지 않고 풀어야 한다.

주어진 num1, num2가 각각 최대 200자리 이므로 int나 long형으로 변환해서 풀수도 없다.

 

각 자릿수를 나눠서 계산하는게 가장 좋은 형태인 것 같다.

public String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) {
        return "0";
    }
    // ans[i]는 각각 자릿수에 해당하는 숫자의 곱
    // ex) i가 0일 때는 1의 자릿수의 곱 합
    // ex) i가 1일 때는 10의 자릿수의 곱 합
    int[] ans = new int[num1.length() + num2.length()];
    for (int i=0; i<num1.length(); i++) {
        for (int j=0; j<num2.length(); j++) {
            ans[i + j] += (num1.charAt(num1.length() - i - 1) - 48) * (num2.charAt(num2.length() - j - 1) - 48);
        }
    }

    String sum = "";
    // 모여진 각 자릿수의 합을 더해 String 처리
    for (int i=0; i<ans.length-1; i++) {
        int num = ans[i];

        // 합이 10보다 큰 경우 일의자릿수만 기록하고 10의 자릿수는 다음 자릿수로 이동해 더해준다.
        ans[i] = num % 10;
        ans[i+1] += num / 10;
        sum = ans[i] + sum;
    }

    // 맨 앞자리 수가 0이 아니라면 더하기
    if (ans[ans.length -1] != 0) {
        sum = ans[ans.length - 1] + sum;
    }

    return sum;
}