LeetCode: 43번 (Multiply Strings) [JAVA]

문제 링크

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

Multiply Strings - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 두 숫자 문자열을 곱하게 되었을 때 값이 저장될 배열을 생성
2. 이후 각 숫자 문자열에서 숫자를 하나씩 가져와 2개를 곱한 결과값을 자릿수를 고려한 배열 위치에 저장
3. 그 다음 일의 자리 누적값부터 앞으로 증가하며 현재 누적값이 10 이상인 경우 일의 자리를 제외한 나머지를 10으로 나눈 값을 다음 자리 누적값으로 이동
4. 해당 위치 결과값을 StringBuilder에 추가
5. 결과 문자열 StringBuilder의 앞 부분 0을 제거 후 반환

 문제 자체는 일종의 곱셈에 대한 문제이지만, 문제 조건 상 내부 BigInteger 라이브러리나 받은 숫자 문자열을 바로 숫자 타입으로 변환하는 것을 금지한다. 또한 주어지는 숫자 문자열의 길이도 매우 길어, 일반적인 곱셈 방식으로는 정확한 계산이 불가능해 다른 방식의 곱셈을 적용해야 한다.
 이에 대한 해결로는 우리가 흔히 곱셈을 할 때 하는 방법을 알고리즘으로 적용하면 해결할 수 있다. 사람이 직접 여러 자리 숫자들 간의 곱셈을 진행하는 경우, 우리는 2개의 숫자에서 각각의 특정 자릿수의 숫자를 하나씩 뽑아 이들을 곱한 다음 해당 결과값을 임시적으로 특정 자릿수에 저장해놓고, 이들을 다음 자릿수로 올리는 등의 추가적인 절차를 거친다. 이와 같은 방식을 똑같이 적용해, 우선 두 숫자의 곱셈을 저장하며 자릿수를 구분할 int 배열 하나를 선언한다. 그 다음에는 주어진 숫자 문자열 num1, num2에서 특정 위치 숫자를 가져온다음 2개를 곱한 결과를 각 위치를 합한 자리에 그 결과를 누적한다. 이렇게 되면 각 자릿수에 곱한 결과값이 저장이 되지만, 결과값의 경우 10이상이 들어가 있을 수 있기 때문에 이를 0~9의 값으로 처리하고 나머지는 다음 자릿수로 넘겨주어야 한다. 그렇기 때문에 누적 int 배열의 시작부터 뒤로 가며 해당 결과값들을 적절히 처리해주고, 남은 숫자를 계속해서 StringBuilder의 앞에 붙여준다.
 이후에 최종적으로 StringBuilder에 저장된 문자열이 바로 num1과 num2의 곱셈 결과이지만, 간혹 앞부분에 필요치않은 0들이 붙어있을 수 있기 때문에 이들을 제거해주는 과정을 거친 후 이를 반환해주면 된다.

 

class Solution {
    public String multiply(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int[] acc = new int[num1.length() * num2.length() + 1];
        int num1Digit, num2Digit;

        for (int i = 0; i < num1.length(); i++) {//각 위치의 숫자를 가져와 곱셉 후 해당 자릿수 배열에 저장
            num1Digit = num1.charAt(num1.length() - 1 - i) - '0';

            for (int j = 0; j < num2.length(); j++) {
                num2Digit = num2.charAt(num2.length() - 1 - j) - '0';
                acc[i + j] += num1Digit * num2Digit;
            }
        }

        for (int i = 0; i < acc.length; i++) {//일의 자리부터 거슬러 올라가며 해당 자리 숫자 계산
            if (acc[i] >= 10) {
                acc[i + 1] += acc[i] / 10;
            }
            result.insert(0, acc[i] % 10);
        }

        while (result.charAt(0) == '0' && result.length() > 1) {//앞 부분의 0 제거
            result.deleteCharAt(0);
        }

        return result.toString();
    }
}

결과