[LeetCode] Multiply Strings (Java)

leetcode.com/problems/multiply-strings/

Multiply Strings - LeetCode

 

 

 

번역 : 문자열로 표현된 두 개의 음이 아닌 정수 num1과 num2가 주어지면 문자열로 표현되는 num1과 num2의 곱을 반환합니다. 또한, 내장 BigInteger 라이브러리를 사용하거나 입력을 정수로 직접 변환해서는 안됩니다.

 

 

 

1. 접근 아이디어

 

• 가장 끝의 숫자를 먼저 곱하기위해 num1과 num2중에 작은 것을 우선으로 기준을 잡습니다.
• 각 자리의 곱들이 끝나면 이전 자리의 곱과 더해줍니다.
• 곱과 더하는 과정이 일어날때 carry 변수를 이용하여 올림수를 체크해줍니다.

 

2. 소스 코드

 

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.length() < num2.length()) { //num1 makes bigger than num2
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }
        
        StringBuilder result = new StringBuilder();
        for(int i=num2.length() - 1; i>=0; i--) {
            int carry = 0;
            int n2 = num2.charAt(i) - 48;
            StringBuilder sb = new StringBuilder();
            for(int j=i; j<num2.length() - 1; j++) sb.append("0");
            for(int j=num1.length() - 1; j>=0; j--) {
                int n1 = num1.charAt(j) - 48;
                int sum = (n1 * n2 + carry);
                int rest = sum % 10;
                carry = sum / 10;
                sb.append(rest);
            }
            
            if(carry != 0) sb.append(carry);
            String temp = sb.toString();
            String ret = result.toString();

            if(ret.length() == 0) {
                result.append(temp);
                continue;
            }
            
            //Add each number
            StringBuilder next = new StringBuilder();
            carry = 0;
            for(int m=0; m<temp.length(); m++) {
                int nn1 = temp.charAt(m) - 48;
                if(m >= ret.length()) {
                    int rest = nn1 + carry;
                    if(rest >= 10) {
                        carry = 1;
                        rest -= 10;
                    } else carry = 0;
                    next.append(rest);
                } else {
                    int nn2 = ret.charAt(m) - 48;
                    int rest = nn1 + nn2 + carry;
                    if(rest >= 10) {
                        carry = 1;
                        rest -= 10;
                    } else carry = 0;
                    next.append(rest);
                }
            }
            
            if(carry != 0) next.append(carry);
            result.delete(0, result.length());
            result.append(next.toString());
        }
        
        return result.reverse().toString().startsWith("0") ? "0" : result.toString();
    }
}

 

 

오랜만에 알고리즘을 해서그런지 Medium 난이도 치고 어려운 문제였다.