Leetcode Java Multiply Strings

업데이트:

문제

Link

코드

class Solution {

  public String multiply(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    for (int num : this.getNumberArray(num1, num2)) {
      if (sb.length() != 0 || num != 0) {
        sb.append(num);
      }
    }
    return sb.length() == 0 ? "0" : sb.toString();
  }
  
  private int[] getNumberArray(String num1, String num2) {
    int[] arr = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--) {
      for (int j = num2.length() - 1; j >= 0; j--) {
        int sum = ((num1.charAt(i) - '0') * (num2.charAt(j) - '0')) + arr[i + j + 1];
        arr[i + j] += sum / 10;
        arr[i + j + 1] = sum % 10;
      }
    }
    return arr;
  }

}

결과

Link

설명

  1. 주어진 문자열 num1과 num2의 길이의 합만큼 int 배열을 정의하여, 각 숫자의 곱의 숫자열을 저장할 변수 arr을 정의한다.
    • $1\times1=1$, $9\times9=81$이므로 두 문자열의 곱의 최대 자릿수는 각 문자열의 길이의 합보다 같거나 작다.
  2. 주어진 문자열 num1과 num2를 배열을 이용하여 각 숫자 별 곱을 구한다.
    • 각 문자열을 반대로 반복하여 숫자의 곱을 구하고, 몫이 저장되는 $i + j + 1$의 자리의 숫자를 가져와 합쳐 변수 sum을 정의한다.
    • 변수 sum의 몫인 $\frac{sum}{10}$을 배열 arr의 $i + j$에 더한다.
    • 변수 sum의 나머지인 $sum\mod10$을 배열 arr의 $i + j + 1$에 주입한다.
  3. 반복문을 통해 arr 배열의 값을 StringBuilder에 저장하여, 두 문자열의 곱을 하나의 문자열로 저장하여 주어진 문제의 결과로 반환한다.
    • 동적 문자열의 생성시, 효율적인 메모리 사용을 위해 StringBuilder를 사용한다.
    • 정수는 항상 0이 아닌 숫자로 시작하므로, 만일 첫 문자열에 0이 들어가는 경우를 제외하고 지속적으로 append를 하여 숫자열을 완성한다.

소스

Sample Code는 여기에서 확인 가능합니다.

댓글남기기