[leetcode] 227, 230, 236

227. Basic Calculator II

https://leetcode.com/problems/basic-calculator-ii/

My Answer 1: Accepted (Runtime: 3884 ms - 5.03% / Memory Usage: 16.5 MB - 22.84%)

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ", "")
        operator = ["+", "-", "*", "/"]
        
        stack = []
        num = ""
        cal = 0
        for i in range(len(s)):
            if s[i] not in operator:
                num += s[i]
            else:
                stack.append(num)
                if cal:
                    a = stack.pop()
                    op = stack.pop()
                    if op == "*":
                        stack[-1] = str(int(stack[-1]) * int(a))
                    if op == "/":
                        stack[-1] = str(int(stack[-1]) // int(a))
                    cal = 0
                num = ""
                stack.append(s[i])
                if s[i] == "*" or s[i] == "/":
                    cal = 1
        stack.append(num)
        if cal:
            a = stack.pop()
            op = stack.pop()
            if op == "*":
                stack[-1] = str(int(stack[-1]) * int(a))
            if op == "/":
                stack[-1] = str(int(stack[-1]) // int(a))
        
        while len(stack) > 1:
            a = stack.pop(0)
            op = stack.pop(0)
            if op == "+":
                stack[0] = str(int(a) + int(stack[0]))
            elif op == "-":
                stack[0] = str(int(a) - int(stack[0]))
        
        return int(stack[-1])

우선 공백들 모두 제거 => replace

stack 에 숫자, 연산자를 구분해서 저장
=> 한자리 숫자만 있는게 아니기 때문에 num 에 숫자를 계속 저장해두고 연산자를 만나면 append

저장하다가 *, / 는 미리 계산해줌
다 보고 나서 마지막 숫자도 append 해주고 *, / 인지 확인해서 처리

다시 while 문 돌려서 +, - 연산도 순서대로 처리해준 후 마지막 stack 값 return

시간이 없어서 너무나 노가다로 풀었다...^^

Solution 1: Accepted (Runtime: 68 ms - 92.76% / Memory Usage: 16 MB - 33.40%)

class Solution:
    def calculate(self, s: str) -> int:
        num, presign, stack=0, "+", []
        for i in s+'+':
            if i.isdigit():
                num = num*10 +int(i)
            elif i in '+-*/':
                if presign =='+':
                    stack.append(num)
                if presign =='-':
                    stack.append(-num)
                if presign =='*':
                    stack.append(stack.pop()*num)
                if presign == '/':
                    stack.append(math.trunc(stack.pop()/num))
                presign = i
                num = 0
        return sum(stack)

stack 을 사용한 루션이

아예 s 뒤에 + 를 임의로 붙여서 확인한다
=> 마지막 num 의 처리가 되는 셈

숫자면 num 에 저장하면서 자릿수까지 계산

연산자는 presign 을 이용
=> 맨 처음에는 + 로 초기화했으므로 그냥 num 이 append 됨
+, - 는 부호를 처리해서 append
*, / 는 stack.pop() 해서 바로 연산해서 append

마지막엔 stack 의 합을 return 하면 된다

루션이 논리는 내 풀이와 유사하지만 훨~씬 간단하다..
이걸로 외워두자!!!

---

230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

My Answer 1: Accepted (Runtime: 52 ms - 57.20% / Memory Usage: 18.2 MB - 29.60%)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def func(root):
            if root is None:
                return
            
            func(root.left)
            self.lists.append(root.val)
            func(root.right)
        
        self.lists = []
        func(root)
        
        return self.lists[k-1]

inorder 로 보면서 순서대로 self.lists 에 저장하고
k-1 번째 값 return

---

236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

My Answer 1: Accepted (Runtime: 64 ms - 94.10% / Memory Usage: 27.7 MB - 30.84%)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def func(root):
            if root is None:
                return False
            
            a = False
            if root == p or root == q:
                a = True
            
            l = func(root.left)
            r = func(root.right)
            
            if l*r or l*a or r*a:
                self.ans = root
                return True
            
            if l or r or a:
                return True
            return False
            
        self.ans = root
        func(root)
        
        return self.ans

재귀로

1. root 가 p, q 인지 확인 => a
2. root.left 가 p, q 인지 확인 => l
3. root.right 가 p, q 인지 확인 => r

a, l, r 중에 2 개의 True 가 있으면 그게 가장 가까운 parent 니까 ans update
하나라도 True 가 있으면 return True 해서 부모한테 알려줌