[LeetCode][Java] Multiply Strings

최지수·2022년 2월 5일
0

Algorithm

목록 보기
48/77
post-thumbnail

문제

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

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

제한사항

  • 1 \leq num1.length, num2.length \leq 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

접근

문자열로 된 숫자를 곱한 문자열을 출력하는 문제입니다. BigInteger나 직접적인 형변환을 거치지 않고 푸는 조건도 추가되었어요. 기수를 고려한 각 숫자를 곱하는 함수를 만들고 나온 문자열을 더하는 함수를 추가하는 식으로 전개를 했습니다.

여담이지만 이런 조건이 붙는 문제는 어디까지 허용하는지 헷갈려요. 이런 문제를 해결하는 과정에서 조건을 잘 이해하고 최대한 활용할 수 있는 역량을 길러야 문제 해결을 제대로 할 수 있다는 교훈을 얻게 되네요. Pass는 했지만 속도 면에선 만족스럽진 못했어요. 교훈을 얻는 것에 만족해야겠네요 ㅎㅎ.

답안

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.charAt(0) == '0' || num2.charAt(0) == '0')
            return "0";
        
        StringBuilder sb = new StringBuilder();

        for(int n2 = num2.length() - 1; n2 >= 0; --n2){
            char digit2 = num2.charAt(n2);
            for(int n1 = num1.length() - 1; n1 >= 0; --n1){
                char digit1 = num1.charAt(n1);
                int radix = (num1.length() - 1 - n1) + (num2.length() - 1 - n2);
                StringBuilder sbMul = multiply(digit1, digit2, radix);
                sb = add(sb, sbMul);
            }
        }

        return sb.toString();
    }

    private StringBuilder multiply(char num1, char num2, int radix){
        StringBuilder sb = new StringBuilder("" + ((num1 - '0') * (num2 - '0')));
        for(int r = 0; r < radix; ++r){
            sb.append('0');
        }
        return sb;
    }

    private StringBuilder add(StringBuilder num1, StringBuilder num2){
        StringBuilder sb = new StringBuilder();
        int i1 = num1.length() - 1;
        int i2 = num2.length() - 1;

        int rad10 = 0;
        while(i1 >= 0 && i2 >= 0){
            int value = rad10 + (num1.charAt(i1--) - '0') + (num2.charAt(i2--) - '0');
            sb.insert(0, "" + (value % 10));
            rad10 = value / 10;
        }
        
        while(i1 >= 0){
            int value = rad10 + ((num1.charAt(i1--) - '0'));
            sb.insert(0, "" + (value % 10));
            rad10 = value / 10;
        }
        
        while(i2 >= 0){
            int value = rad10 + ((num2.charAt(i2--) - '0'));
            sb.insert(0, "" + (value % 10));
            rad10 = value / 10;
        }
        
        // 마지막에 모두 연산한 이후에 다음 기수가 남아있는 경우
        if(rad10 > 0){
            sb.insert(0,"" + rad10);
        }

        return sb;
    }

}
profile
#행복 #도전 #지속성

0개의 댓글