TIL 21/05/13

1.

코딜리티 레슨 pdf를 읽던중 range의 경우 메모리를 많이 할당한다고 한다. 근데 이 내용은 python2에 해당하는 내용이고 현재 python3에서는 range와 xrange동일한 방식으로 메모리를 할당한다고함.

다음 블로그에서는 다음과 같은 말을 한다

하지만, xrange() 를 실행할 경우는 동작 방식이 조금 다르다. 자신에 속한 데이터값을 한꺼번에 메모리에 로드 하는 것이 아니라 해당 값에 접근 할때마다 그 값을 하나씩 로딩하는 방식이다. 그 구조가 마치 generator의 yield 를 사용했을때와 동일한 효과라고 생각하면 된다.

https://bluese05.tistory.com/57

2

리트코드의 Valid Perfect Score 문제를 다음과 같이 풀었다.

x
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
​
        for i in range(1, 2**31-1):
            if i*i > num:
                return False
​
            if i*i == num:
                return True

다른 사람을 풀이를 봤는데

x
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        square = int(num**(1/2))
        return square*square == num

훨씬 깔끔하다. 본받도록 하자

3

리트코드 Symmetric Tree를 풀어보려고 했다.

근데 Input이 root = [1,2,2,3,4,4,3] 이런형식이길레 리스트로 주어지는줄 알았는데 클래스로 구현된 TreeNode가 input으로 들어오는거여서 삽질햇다;

나는 입력값이 리스트라고 가정하고 다음과같이 구현했다.

x
# 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 isSymmetric(self, root: TreeNode) -> bool:
        root1 = [1,2,2,None,3,None,3]
        length = len(root1)
​
        for i in range(1, 10):
            if 2**i-1 == length:
                iterNum = i
                break
                
        if iterNum == 1:
            return True
        
        if iterNum == 2:
            if root1[1] == root1[2]:
                return True
            else:
                return False
            
        for i in range(3, iterNum):
            leftStartIndex = 2**(i-1) - 1 
            rightEndIndex = 2*leftStartIndex
            midLength = (rightEndIndex - leftStartIndex + 1) // 2
            leftEndIndex = leftStartIndex + midLength - 1
            # rightStartIndex = rightEndIndex - midLength + 1
            for i in range(leftStartIndex, rightEndIndex+1):
                if root1[i] != root1[rightEndIndex + leftStartIndex - i]:
                    return False
                if leftEndIndex > i:
                    break
        return True

당연히 틀렸다고 나온다;; 그래서 별도로 VSCODE에 리스트 인풋을 줬을때 잘 동작함

재귀로 풀면 다음과 같이 풀 수 있다.

x
# 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 isSymmetric(self, root: TreeNode) -> bool:
        if root == None: # 아무것도 없으면 대칭이니까 True 반환
            return True
​
        return self.checkSymmetric(root.left, root.right)
​
    def checkSymmetric(self, leftNode, rightNode):
​
        if leftNode == None or rightNode == None: # 둘중 하나만 None 이면 False, 둘다 None이면 True
            return leftNode == rightNode
​
        if leftNode.val != rightNode.val: # 두 노드가 모든 None이 아니지만 값이 다르면 False
            return False
​
        # 이후 재귀를 돌면서 대칭인지 확인
        return self.checkSymmetric(leftNode.left, rightNode.right) and self.checkSymmetric(leftNode.right, rightNode.left)
​