415. Add Strings (Math, String, Simulation)

링크 - https://leetcode.com/problems/add-strings/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

이 문제는 각 string의 맨 끝부터 차례대로 계산하면서 답을 더해가는 방식으로 풀면 된다. 중요한것은 carry를 사용해서 이전에 더한 값이 10이 넘을때의 값을 추적해야 한다는 점이다.

Code

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        ans = ""

        i1 = len(num1) - 1
        i2 = len(num2) - 1
        carry = 0

        while i1 >= 0 or i2 >= 0:
            if i1 < 0:
                calc = carry + int(num2[i2])
                cur_ans, carry = calc % 10, calc // 10
                ans = str(cur_ans) + ans
                i2 -= 1
            elif i2 < 0:
                calc = carry + int(num1[i1])
                cur_ans, carry = calc % 10, calc // 10
                ans = str(cur_ans) + ans
                i1 -= 1
            else:
                calc = carry + int(num1[i1]) + int(num2[i2])
                cur_ans, carry = calc % 10, calc // 10
                ans = str(cur_ans) + ans
                i1 -= 1
                i2 -= 1

        return ans if carry == 0 else str(carry) + ans

Complexity

n1 = length of num1, n2 = length of num2

Time Complexity: O(max(n1, n2))

Space Complexity: O(max(n1, n2)) 왜냐하면 ans는 길이가 최대 max(n1, n2) + 1이기 때문이다.