227. Basic Calculator II (Math, String, Stack)

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

난이도 - Medium

Intuition

1) Stack

이 문제는 이전의 숫자와 부호를 잘 트랙킹해야하는 문제이다. 따라서 stack을 통해 이를 트랙킹하는 방법을 생각할 수 있다.

1. s의 모든 글자를 for문이나 while문으로 탐색한다. 만약 글자가 숫자이면(Python은 c.isdigit()으로 판별가능), 현재 숫자를 cur_num = cur_num * 10 + int(c)로 업데이트한다.

2. 만약 글자가 +-*/중 하나이거나 마지막 글자이면, 우리는 스택에 있는 숫자를 업데이트해야한다.

3. 스택에 있는 모든 숫자를 더한다.

class Solution:
    def calculate(self, s: str) -> int:
        idx = 0
        cur_num = 0
        cur_op = '+' # Initialize first operation as "+"
        stack = []

        for i in range(len(s)):
            c = s[i]
            if c.isdigit():
                cur_num = cur_num * 10 + int(c)
            # Update current number and operation when we meet new operation or at the end of the string
            if c in "+-*/" or i == len(s) - 1:
                if cur_op == "+": stack.append(cur_num)
                if cur_op == "-": stack.append(-cur_num)
                if cur_op == "*": stack.append(stack.pop() * cur_num)
                if cur_op == "/": stack.append(int(stack.pop() / cur_num))
                cur_num, cur_op = 0, c

		# The answer is the whole sum of the stack
        return sum(stack)

Time Complexity: O(n) 우리는 linear하게 각 글자를 탐색하기 때문이다.

Space Complexity: O(n) stack을 사용하므로 stack을 담을 최대 크기는 n이기 때문이다.

2) Optimized without the stack

우리는 stack 없에 O(1) space complexity로 이 문제를 풀 수 있다. 우리가 트래킹해야 하는 숫자는 last_num과 curr_num이다. last_num은 +나-가 나올때마다 답에 더해주고, *나/가 나오면 last_num을 계속 curr_num을 통해서 업데이트 해야한다.

class Solution:
    def calculate(self, s: str) -> int:
        ans = 0

        n = len(s)
        curr_num = last_num = 0
        operation = "+"
        for i in range(n):
            c = s[i]
            if c.isdigit():
                curr_num = curr_num * 10 + int(c)
            if c in "+-*/" or i == n-1:
                if operation == "+":
                    ans += last_num
                    last_num = curr_num
                elif operation == "-":
                    ans += last_num
                    last_num = -curr_num
                elif operation == "*":
                    last_num *= curr_num
                elif operation == "/":
                    last_num = int(last_num / curr_num)
                curr_num = 0
                operation = c
            
        ans += last_num
        return ans

Time Complexity: O(n) 우리는 linear하게 각 글자를 탐색하기 때문이다.

Space Complexity: O(1)