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.
num1
and num2
consist of digits only.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;
}
}