개발/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"

성능이 너무 좋지 않아서 다른 사람들은 어떻게 했지? 라는 궁금증에 살펴보니..