input :
- num1, num2
output :
- 두 수의 곱셈 결과를 문자열로 반환하시오.
조건 :
- BigInteger와 같은 라이브러리를 사용하지 마시오.
Solution explain : Solution1
idea
- 물론 짜증나면 그냥 파이썬의 형변환을 써서 하면 되긴 한다.
- 곱셈을 실제로 하듯 결과를 dp에 저장하면서 하자.
주의
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if len(num1) < len(num2):
num1, num2 = num2, num1
# temp_idx를 통해 어디서부터 계산 결과를 넣을지 정한다.
length2 = len(num2)
dp = [0] * (len(num1) * 2)
temp_idx = len(dp)
for i in range(length2 - 1, -1, -1):
# dp의 저장위치는 계속 앞으로 1칸씩 당겨지므로 연산을 한다.
temp_idx -= 1
for j in range(len(num1) - 1, -1, -1):
value = int(num1[j]) * int(num2[i])
# len(num1)과의 변위로 idx를 더 앞으로 움직여야 하면 더 땡긴다.
idx = temp_idx - (len(num1) - 1 - j)
temp_sum = value + dp[idx]
carry = temp_sum // 10
dp[idx] = temp_sum % 10
idx -= 1
while carry:
dp[idx] += carry
carry = dp[idx] // 10
dp[idx] = dp[idx] % 10
idx -= 1
ret, flag = "", 0
for item in dp:
if not flag and item != 0:
flag = 1
if flag:
ret += f"{item}"
return "0" if ret == "" else ret