728x90

LeetCode-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.
note : Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

        :::python

class Solution: def multiply(self, num1: str, num2: str) -> str: if (num1=='0') or (num2=='0'): return '0' return str(int(num1)*int(num2))

Result : 19ms Memory: 13.9mb

using dict

        :::python

class Solution: def multiply(self, num1: str, num2: str) -> str: num_dict = { "0":0 ,"1":1 ,"2":2 ,"3":3 ,"4":4 ,"5":5 ,"6":6 ,"7":7 ,"8":8 ,"9":9 } i=0 answer = '' s = 0 for nu, n1 in enumerate(num1[::-1]): for nu2, n2 in enumerate(num2[::-1]): s += num_dict[n1]*10(nu)*num_dict[n2]*10nu2 return str(s)

Result : 230ms Memory: 14mb

Multiply Strings

Multiply Strings๋Š” ๋‘ ๊ฐœ์˜ ๋ฌธ์ž์—ด์„ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›์•„์„œ, ๋‘ ๋ฌธ์ž์—ด์ด ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž๋ฅผ ๊ณฑํ•œ ๊ฒฐ๊ณผ๋ฅผ ๋ฌธ์ž์—ด ํ˜•ํƒœ๋กœ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค.

๋ฌธ์ œ ์„ค๋ช…

์˜ˆ๋ฅผ ๋“ค์–ด, ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์ด "123"๊ณผ "456"์ธ ๊ฒฝ์šฐ, ๋‘ ์ˆซ์ž๋ฅผ ๊ณฑํ•œ ๊ฒฐ๊ณผ๋Š” "56088"์ด ๋œ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๋ช…

์ฃผ์–ด์ง„ ๋ฌธ์ œ์—์„œ๋Š” ๋ฌธ์ž์—ด๋กœ ํ‘œ์‹œ๋œ ๋‘ ์ˆซ์ž๋ฅผ ๊ณฑํ•œ ๊ฒฐ๊ณผ๋ฅผ ๋ฌธ์ž์—ด ํ˜•ํƒœ๋กœ ๋ฐ˜ํ™˜ํ•ด์•ผํ•œ๋‹ค. ์ด๋ฅผ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

  1. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ๋ฌธ์ž์—ด์„ ๋’ค์ง‘๋Š”๋‹ค.
  2. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด ์ค‘ ๊ธธ์ด๊ฐ€ ์งง์€ ๋ฌธ์ž์—ด์„ ๊ธฐ์ค€์œผ๋กœ ์ˆซ์ž๋ฅผ ํ•˜๋‚˜์”ฉ ๊ฐ€์ ธ์™€์„œ, ๊ธด ๋ฌธ์ž์—ด๊ณผ ๊ณฑํ•œ๋‹ค.
  3. ๊ณฑ์…ˆ ๊ฒฐ๊ณผ๋ฅผ answer๋ผ๋Š” ๋ณ€์ˆ˜์— ๋”ํ•ด์ค€๋‹ค. answer๋Š” ์ดˆ๊ธฐ๊ฐ’์œผ๋กœ 0์„ ๊ฐ€์ง„๋‹ค.
  4. ๋งˆ์ง€๋ง‰์œผ๋กœ, answer์— ์ €์žฅ๋œ ๊ฐ’์„ ๋‹ค์‹œ ๋’ค์ง‘์–ด์„œ ๋ฆฌํ„ดํ•œ๋‹ค.

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‘ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๊ฐ€ ์ตœ๋Œ€ 10^4์ธ ๊ฒฝ์šฐ์—๋„ ์ž‘๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(nm)์ด ๋œ๋‹ค. (n์€ ๋ฌธ์ž์—ด1์˜ ๊ธธ์ด, m์€ ๋ฌธ์ž์—ด2์˜ ๊ธธ์ด)

์˜ˆ์‹œ ์ฝ”๋“œ

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        num1, num2 = num1[::-1], num2[::-1]
        m, n = len(num1), len(num2)
        ans = [0] * (m + n)
        for i in range(m):
            for j in range(n):
                ans[i+j] += int(num1[i]) * int(num2[j])

        carry = 0
        for i in range(m+n):
            temp = ans[i] + carry
            ans[i] = temp % 10
            carry = temp // 10

        while len(ans) > 1 and ans[-1] == 0:
            ans.pop()

        return ''.join(map(str, ans[::-1]))

์œ„ ์ฝ”๋“œ๋Š” Python์œผ๋กœ ์ž‘์„ฑ๋œ Multiply Strings์˜ ์˜ˆ์‹œ ์ฝ”๋“œ์ด๋‹ค. ์ฝ”๋“œ์˜ ์ „๋ฐ˜์ ์ธ ๋ถ€๋ถ„์—์„œ๋Š” ์œ„์—์„œ ์„ค๋ช…ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์œ ์‚ฌํ•œ ๋ฐฉ๋ฒ•์ด ์‚ฌ์šฉ๋˜๊ณ  ์žˆ๋‹ค. ๋‹จ, ๋””ํ…Œ์ผํ•œ ๋ถ€๋ถ„์€ ์ฝ”๋“œ๋ฅผ ๋ณด๋ฉด์„œ ์ดํ•ด๋ฅผ ํ•˜๋„๋ก ํ•˜์ž.

๋ฐ˜์‘ํ˜•

'๐Ÿข One step' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[leetcode-48] Rotate Image  (0) 2023.04.30
[leetcode-347] Top K Frequent Elements  (0) 2023.04.27
[leetcode-14] Longest Common Prefix  (0) 2023.04.24
[leetcode-12] Integer to Roman  (0) 2023.04.21
[leetcode-10] Regular Expression Matching  (0) 2023.04.20
๋‹คํ–ˆ๋‹ค