[leetcode] 102, 103, 172, 190

172. Factorial Trailing Zeroes

https://leetcode.com/problems/factorial-trailing-zeroes/

My Answer 1: Accepted (Runtime: 5754 ms - 11.80% / Memory Usage: 14 MB - 98.17%)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        fac = 1
        
        while n:
            fac *= n
            n -= 1
            
        fac = str(fac)
        ans = 0
        
        for i in range(len(fac)-1, -1, -1):
            if fac[i] == "0":
                ans += 1
            else:
                break
        
        return ans

1 부터 n 까지의 팩토리얼을 구해서 string 으로 바꾸고 맨 뒤부터 0 의 개수 세주기

logarithmic 이 아니라서 매우 느리다..^^

My Answer 2: Accepted (Runtime: 32 ms - 76.09% / Memory Usage: 14.4 MB - 22.91%)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        cnt = n
        while cnt:
            cnt = cnt // 5
            ans += cnt
        
        return ans

어떻게 하면 더 빨리 할 수 있을까 하다가 생각해보니..
맨 뒤의 0 의 개수는 10 = 2*5 와 관련이 있음

2 와 5 의 개수 중 최솟값 = 0 의 개수 가 되는 것~
근데 2 는 무조건 5 보다 많으니까 5 의 개수만 알아내면 됨

5 의 거듭 제곱까지 고려해서 계속 5 로 나눈 개수를 더해주면 끝~

---

190. Reverse Bits

https://leetcode.com/problems/reverse-bits/

My Answer 1: Accepted (Runtime: 28 ms - 88.74% / Memory Usage: 14 MB - 97.15%)

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        b = str(bin(n))[2:]
        
        while len(b) < 32:
            b = "0" + b
        b = ''.join(reversed(b))
        
        ans = int(b, 2)
        
        return ans

이진수를 문자열로 바꿔서 reverse 해주기

Solution 1: Accepted (Runtime: 37 ms - 12.42% / Memory Usage: 14.1 MB - 88.89%)

class Solution:
    def reverseBits(self, n: int) -> int:
        out = 0
        for i in range(32):
            out = (out << 1)^(n & 1)
            n >>= 1
        return out

out = 0 , n = 11011010

out = 0, n = 1101101
out = 01, n = 110110
out = 010, n = 11011
out = 0101, n = 1101
out = 01011, n = 110
out = 010110, n = 11
out = 0101101, n = 1
out = 01011011, n = 0

이런식으로 된다는데...

비트는 어렵다...

https://leetcode.com/problems/reverse-bits/discuss/732138/Python-O(32)-simple-solution-explained

---

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

My Answer 1: Accepted (Runtime: 32 ms - 82.37% / Memory Usage: 14.7 MB - 45.11%)

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        queue = [root]
        
        while queue:
            level = len(queue)
            tmp = []
            for i in range(level):
                r = queue.pop(0)
                if r:
                    tmp.append(r.val)
                    if r.left:
                        queue.append(r.left)
                    if r.right:
                        queue.append(r.right)
            if tmp:
                ans.append(tmp)
        
        return ans

queue 를 사용해서 레벨 단위로 노드들 저장
각 레벨마다 다시 for 문 돌려서 tmp 에 값들 append & queue 에 다음 레벨 값들 append
하나의 레벨을 다 봤으면 ans 에 append

---

103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

My Answer 1: Accepted (Runtime: 28 ms - 88.39% / Memory Usage: 14.7 MB - 13.04%)

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        queue = [root]
        zigzag = 0
        
        while queue:
            level = len(queue)
            tmp = []
            for i in range(level):
                r = queue.pop(0)
                if r:
                    tmp.append(r.val)
                    if r.left:
                        queue.append(r.left)
                    if r.right:
                        queue.append(r.right)
            if tmp:
                if zigzag:
                    tmp = tmp[::-1]
                ans.append(tmp)
                zigzag = not zigzag
        
        return ans

102 번에서 zigzag 만 추가

zigzag 를 0 <-> 1 번갈아주면서 1 일때만 reverse 해서 append => tmp[::-1]