[AlphaGo Study] [LeetCode] [JAVA] 43. Multiply Strings

문제 설명

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

제한 사항

☞ The length of both num1 and num2 is < 110.

☞ Both num1 and num2 contain only digits 0-9.

☞ Both num1 and num2 do not contain any leading zero, except the number 0 itself.

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

입출력 예

Input		Output
num1	num2
"2"	"3"	"6"
"123"	"456"	"56088"

입출력 예 설명

#예제1

문자열(String) 2와 3을 곱셈(연산)하여 문자열(String) 6이 결과값으로 나온다.

 

leetcode.com/problems/multiply-strings/

Multiply Strings - LeetCode

---

문제를 풀기 전 THINK

  § 곱셈 결과의 길이의 최대는 두 수의 길이를 더한 것과 같음. ex) 999*999=998001

  § 값이 없거나 0일 경우 각각 빈 값과 0 return.

  § 뒷 자리부터 곱셈을 시작하므로 제일 큰 값에서 -1씩 내려감.

  § 숫자를 num1, num2에서 각각 하나씩 추출하여 곱셈을 함.

  § 이 때, if문을 사용하여 몫과 나머지를 구하여 각각 변수에 넣어줌.

  § i + j = 0일때, 더 이상 앞으로 넘길 값이 없으므로 if문에 들어가지 않도록 함.

  § 결과를 출력할 때, i = 0으로 시작하므로 res_len에서 -1한 값까지 for문을 돌림.

나의 Solution

public class MultiplyStrings {
	public static String multiply(String num1, String num2) {
		int num1_len = num1.length();
		int num2_len = num2.length();
		int res_len = num1_len + num2_len; // 곱셈 결과의 길이의 최대는 두 길이를 더한 것과 같음 ex) 999*999=998001
		int[] res = new int[res_len];
		
		StringBuilder result = new StringBuilder();
		
		// 값이 없으면 빈 값 return
		if(num1 == null || num2 == null) {
			return "";
		} // if end
		
		// 0을 곱하면 0이므로 둘 중 하나만 0이어도 0을 return
		if(num1.equals("0") || num2.equals("0")) {
			return "0";
		} // if end
		
		// 맨 뒷 자리부터 곱셈 시작
		for(int i = num1_len - 1; i >= 0; i--) {
			for(int j = num2_len - 1; j >= 0; j--) {
				
				int num1_int = num1.charAt(i) - '0'; // 숫자 하나 추출
				int num2_int = num2.charAt(j) - '0';
				
				res[i + j] += num1_int * num2_int; // 넘겨온 숫자와 곱한 값을 더함
				
				// i + j = 0 이면 더 이상 앞으로 넘길 값이 없음
				if(res[i + j] >= 10 && i + j != 0) {
					res[i + j - 1] += res[i + j] / 10; // 몫을 다음 자릿 수에 넘겨서 더함 ex) 18이면 1을 넘겨줌
					res[i + j] = res[i + j] % 10; // 나머지를 저장
				} // if end
			} // for end
		} // for end
		
		// 0 부터 시작이므로 res_len에서 1 뺌
		for(int i = 0; i < res_len - 1; i++) {
			result.append(res[i]);
		} // for end
		
		return result.toString();
	}
}

Comment...

처음에 if문에서 i + j != 0 의 조건을 줄 생각을 하지 못했다. 이클립스에서는 돌아가서 leetcode에서도 Submit 해봤는데 돌아가지 않았다...ㅠㅠ 그래서 결과를 찾은 것이 이것!

그리고 res[i + j] += num1_int * num2_int 이것도 처음엔 + 할 생각을 하지 못하고 단순하게 값만 대입해주었다. 그랬더니 값이 더해지지 않고 이상하게 출력되었다..ㅜ 찾느라 힘들었다....