[LeetCode] 43. Multiply Strings(Java, Multiply)

leetcode.com/problems/multiply-strings/

Multiply Strings - LeetCode

 

## 접근방법

---

대부분의 수학문제들은 수학적 풀이 사고가 있다면 쉽게 해결할 수 있다. 곱셈을 배웠을 때를 기억해보자. 

 

 

여러 자리 수의 곱셈을 할 때, 위에 길이가 긴 수를 두고 아래에 길이가 짧은 수를 두고 연산을 시작한다. 아래의 길이가 짧은 수를, 위의 수와 자릿수에 맞게끔 곱셈을 하고, 모든 과정에서 나온 수들을 더하게 된다.

 

 

곱셈과 덧셈에서는 캐리가 발생하므로, 캐리를 잘 처리하는 것이 핵심이다. 코드 작성에서 고민했던 부분은, 마지막에 발생된 캐리는 별도로 처리가 필요하게끔 설계가 되어 있다. 마지막 캐리가 발생했을때, 이 캐리는 최대 10을 넘지 못한다는 사실을 이용하면 간단해진다.

 

 

위의 이유에 대해서 생각해보자. n자리 수와 m자리 수를 곱했을 때, 최대 나올 수 있는 자리수는 n + m이다. n이 100이고 m이 100일 때, 다섯 자리가 나오게 된다. 그렇다면, 두 자리의 곱은 최대 네 자리만 발생한다는 사실을 깨달을 수 있다.

 

 

이 사실을 이용해서, 마지막 캐리는 절대 10을 넘지 못한다는 것을 증명할 수 있다. 추가적으로 덧셈에서 발생할 수 있는 캐리의 최댓값도 1이라는 사실을 알고  있도록 하자.

 

 

두번째 풀이는 다른 사람의 코드를 참고했다. 가장 직관적이고 효율적인 코드가 아닐까 싶다.

 

## 해설코드

---

class Solution {
    public String multiply(String num1, String num2) {
        int[] result = new int[num1.length() + num2.length()];
        int carry = 0;
        int n1, n2;
        
        if(num1.length() < num2.length()){
            String str = num1;
            num1 = num2;
            num2 = str;
        }
        
        int rIdx = result.length - 1;
        
        for(int i = num2.length() - 1; i >= 0; i--){
            int idx = rIdx; 
            
            for(int j = num1.length() - 1; j >= 0; j--){
                n1 = Integer.valueOf(num1.charAt(j) - '0');
                n2 = Integer.valueOf(num2.charAt(i) - '0');
                
                int m = n1 * n2;
                int q = m /10;
                int r = (m % 10 + carry);
                
                if(r >= 10){
                    result[idx] += r % 10;
                    carry = 1 + q;
                }else{
                    result[idx] += r;
                    carry = q;
                }
                
                if(result[idx] >= 10){
                    result[idx] = result[idx] % 10;
                    carry += 1;
                }
                
                idx -= 1;
            }
            
            if(carry > 0){
                result[idx] += carry;
                carry = 0;
            }
            
            rIdx -= 1;
        }
        
        StringBuilder sb = new StringBuilder("");
        int start = 0;
        boolean chk = false;
        
        while(start < result.length){
            if(!chk && result[start] != 0)
                chk = true;
            
            if(chk)
                sb.append(result[start]);
            
            start += 1;
        }
        
        if(sb.toString().length() == 0)
            return "0";
        
        return sb.toString();
    }
}

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 n1 = Integer.valueOf(num1.charAt(i) - '0');
                int n2 = Integer.valueOf(num2.charAt(j) - '0');
                
                result[i + j + 1] += n1 * n2;
            }
        }
        
        for(int i = result.length - 1; i > 0; i--){
            result[i - 1] += result[i] / 10;
            result[i] = result[i] % 10;
        }
        
        boolean chk = false;
        StringBuilder sb = new StringBuilder("");
        
        for(int i = 0; i < result.length; i++){
            if(result[i] != 0 && !chk)
                chk = true;
            
            if(chk) sb.append(result[i]);
        }
        
        if(sb.toString().length() == 0) return "0";
        
        return sb.toString();
    }
}