LeetCode(43)::Multiply Strings

문제

Multiply Strings - LeetCode

문제파악

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

→ 즉, 2개의 문자열로 표현된 양수가 들었을때 두스의 곱을 문자열로 표현하라~!!

• 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. → 06, 0027 같이 앞에 0이 오는 수가 없다.

문제풀이

이 문제 또한 곱셈이 이루어 지는 과정을 살펴보면 여러가지 방법으로 코드진행이 될 수 있을 것 같다.(물론 큰 틀에서는 같은 느낌)

 

우선 기본적인 곱셈의 방식을 생각해보면 다음과 같다.

다만.. carry를 가장 마지막에 넘겨주는 방향으로 생각하면 다음과 같다.

일단 각 인덱스에 각자리수의 합을 구해놓고 거기에 해당하는 carry 더해주면 된다. 각 인덱스 기준으로 확인해 보면 다음과 같다.

각 인덱스  num1[i]*num2[j] = mul[i+j+1] 위치에 더해준다.  해당위치에서 캐리를 올려주고 더해준다.

그리고 그 결과를 String으로 변화해서 출력해주면 된다.

class Solution {
    public String multiply(String num1, String num2) {
        int[] result = 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 int_num1 = Integer.valueOf(num1.charAt(i) - '0');
                int int_num2 = Integer.valueOf(num2.charAt(j) - '0');
                result[i + j + 1] += int_num1 *  int_num2;
            }
        }
    
        
        
        for(int i = result.length-1; i> 0;i--){
            result[i - 1] += result[i]/10;
            result[i] %= 10;
        }
        
        StringBuilder sol = new StringBuilder("");
        boolean start_chk = false;
        
        for(int i = 0; i < result.length; i++){
            if(result[i] != 0 && !start_chk){
                start_chk = true;
            }
            
            if(start_chk)sol.append(result[i]);
        }

        if(sol.length() == 0){
            return "0";
        }
        
        return sol.toString();
    }
}

주의할 점!!!

주의할 점으로는 곱셈결과를 저장한 테이블에서 String으로 append 해줄때 첫 시작 지점을 잡아줘야한다.

0을 곱하게 되거나 index = 1에 carry가 없다면 0으로 시작되게 되기 때문이다. 

 

즉, 시작위치를 잡아서 append시켜줘야하지 그렇지 않을경우 012혹은 000과 같은 0으로 시작하는 결과가 발생할수 있다.