개발/Leetcode
Leetcode 43. Multiply Strings
지산동고라니
2023. 7. 1. 11:36
https://leetcode.com/problems/multiply-strings/description/
Multiply Strings - LeetCode
Can you solve this real interview question? 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. Note: You must not use any built-in BigInteger library
leetcode.com
문제
양의 정수인 num1과 num2가 주어지며 이 숫자들은 문자열로 표현되어있다. 이때 num1과 num2의 곱을 문자열로 반환하여라
주의: 내부 라이브러리인 BigInteger나 그와 관련된 라이브러리는 쓰지말 것!
코드
class Solution:
def multiply(self, num1: str, num2: str) -> str:
c = 0
l_num1 = len(num1)
l_num2 = len(num2)
n1 = num1[::-1]
n2 = num2[::-1]
answer = [0] * (l_num1 + l_num2 + 1)
for i in range(l_num1):
for j in range(l_num2):
m = int(n1[i]) * int(n2[j]) + c + answer[i+j]
# print(f"{n1[i]} * {n2[j]}")
c = m // 10
answer[i+j] = m % 10
if c != 0:
answer[(i) + (l_num2)] += c
# print(answer)
c = 0
r = "".join(map(str, answer[::-1])).lstrip('0')
return r if r else "0"
성능이 너무 좋지 않아서 다른 사람들은 어떻게 했지? 라는 궁금증에 살펴보니..