원티드 프리온보딩 3-1 알고리즘 (2)

wodnr_P·2023년 9월 7일

leetcode 알고리즘 원티드 원티드 프리온보딩 프리온보딩

LeetCode Top Interview 150

목록 보기

13/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Binary Tree Right Side View

[Quetion]

LeetCode 199. Binary Tree Right Side View

📌 접근법

[문제 이해]

트리를 오른쪽에서 보았을 때, 보이는 노드 값을 반환

처음 접근할 때, 문제에서 요구하는 상황을 예상해볼 때 고려되는 사항은 다음과 같이 생각했다.

오른쪽 노드가 없는 경우, 왼쪽이 오른쪽에서 보이므로 왼쪽 노드 출력이 필요
왼쪽과 오른쪽 깊이를 알고, 오른쪽이 왼쪽 보다 짧을 경우 왼쪽노드 값 탐색

그래서 오른쪽과 왼쪽 크기 차이만큼 리스트를 슬라이싱해서 결과 리스트에 붙이기를 생각했다.

# 실패한 시도
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        l_root = root
        l,r = [], []
        self.left_search(l_root, l)
        self.right_search(root, r)

        if len(r) >= len(l):
            return r
        else:
            l[:] = r[:] + l[len(r):]
            return l 

    def left_search(self, node, l):
        if node is not None:
            l.append(node.val)
            print(l)
            if node.left:
                self.right_search(node.left, l)
            else:
                if node.right:
                    self.left_search(node.right, l)   

    def right_search(self, node, r):
        if node is not None:
            r.append(node.val)
            print(r)
            if node.right:
                self.right_search(node.right, r)
            else:
                if node.left:
                    self.left_search(node.left, r)

현재 코드는 재귀적으로 오른쪽 노드가 있으면 탐색하고, 없을 경우 왼쪽 노드에서 오른쪽 리프 노드로 우선 탐색하는 방법으로 노드들을 순회한 후, 오른쪽 노드의 깊이보다 왼쪽 노드의 깊이가 깊으면 그만큼 슬라이싱 한다.

하지만 이 코드에서 가장 문제점은 오른쪽 노드가 왼쪽 노드들 보다 깊이가 얕을 때, 왼쪽 노드들의 리프 노드들을 탐색하는 과정에서 오른쪽 리프 노드만 탐색하기 때문에 왼쪽 리프 노드는 탐색하지 않는 오류가 있다.

그래서 깊이 별로 순회하는 방법으로는 안되겠다고 판단하여 BFS(너비우선탐색) 방법을 활용해보기 위해 알아보았고, 각 노드들을 레벨 별로 저장하는 방법을 생각했다.

각 노드들을 순회할 때, 해당 노드들의 레벨도 같이 저장하며 판단
오른쪽 트리를 우선 순회하며 같은 레벨의 노드는 리스트 형식으로 저장 ex) 0레벨 - 1, 1레벨 - 4, 3 = [0,[4,3]]
오른쪽 트리를 우선 순회했기 때문에 중첩 리스트 속 첫번째 값은 오른쪽 노드
리스트 컴프리헨션으로 순회를 마친 결과 리스트의 첫번째 값만 리스트에 새로 저장

💻 구현

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    	# 탐색하며 저장할 리스트
        l=[]
        self.level_search(root, l)
        l = [i[0] for i in l]
        
        return l
        
	# BFS 탐색 함수 : 오른쪽 우선, 레벨도 함께 판단
    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                if len(l) < level+1:
                    l.append([])
            
                l[level].append(node.val)
         
                if node.right:
                    queue.append((node.right, level+1))
                if node.left:
                    queue.append((node.left, level+1))

        return l

Runtime: 37ms | Memory: 16.2MB
LeetCode 코드 중 Runtime 83%, Memory 74% 해당하는 결과

📝 Binary Tree Right Side View 회고

시간복잡도는 모든 노드를 탐색하므로 노드 개수인 n개 만큼, 탐색 후에는 결과 리스트를 탐색하며 오른쪽 노드 값만 다시 저장하므로 최종 O(n)을 가진다.
공간 복잡도 역시 탐색하며 n번 저장하기 때문에 O(n)의 공간 복잡도를 가진다.
다른 솔루션들도 참고했을 때, BFS 방식을 가장 많이 사용하고 있으며 양방향 큐를 활용하는 방법도 꽤 많았던 것 같다.
아직 BFS, DFS에 익숙하지 않아서 솔루션을 보아도 이 방법보다 좋은 성능으로 개선할 수 있는 아이디어가 떠오르지 않기에 공부를 많이 해야겠다.

# Average of Levels in Binary Tree

[Quetion]

LeetCode 637. Average of Levels in Binary Tree

📌 접근법

[문제 이해]

같은 레벨에 있는 노드들의 평균 값을 리스트로 반환

이번 문제는 Binary Tree Right Side View 문제를 먼저 경험해서 그런지 굉장히 유사한 문제라고 생각되어 아이디어가 바로 떠올랐다.

BFS 방식으로 순회하되, 각 레벨 별로 리스트에 값을 저장 (다중 값 = 중첩리스트 형식)
저장된 리스트를 반복하여 다중 값이면 평균을 구하고, 아니면 단일 값만 반환하여 결과 리스트에 저장

💻 구현

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        # 노드 탐색 결과를 담을 리스트 
        l=[]
        self.level_search(root, l)
        
        # 각 레벨 노드들의 평균 계산 
        l = [sum(i)/len(i) if len(i) >= 2 else sum(i) for i in l]
        return l

    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                if len(l) < level+1:
                    l.append([])
            
                l[level].append(node.val)

                if node.right:
                    queue.append((node.right, level+1))
                if node.left:
                    queue.append((node.left, level+1))

        return l

Runtime: 43ms | Memory: 18.8MB
LeetCode 코드 중 Runtime 98%, Memory 67% 해당하는 결과

📝 Average of Levels in Binary Tree 회고

시간복잡도, 공간복잡도 모두 O(n)을 가진다.
노드들을 순회하며 같은 레벨 별로 저장하는 방법은 Binary Tree Right Side View에서 아이디어를 얻었고, 탐색 결과 리스트에 대해 가벼운 연산만 해결하면 되는 문제였다. 그리고 속도와 메모리 모두 생각보다 좋게 나왔다.
처음에는 이진 검색 트리라고 생각하여 평균을 구할 때 2로 나누었지만, 테스트 케이스에 막혀서 다시 생각해보니 레벨 별로 2개 이상의 노드가 있기 때문에, 각 레벨의 노드를 담은 리스트의 길이로 나누어 해결했다.
다른 솔루션을 참고해보니 BFS가 아닌 DFS 전위순회 방식으로 접근한 코드도 있었다. 저장할 때 마다 해당 노드의 깊이를 카운트하는 방법인 것 같다. 현재 작성한 코드와 성능적으로는 비슷한 Runtime을 가지고 있어 보인다.
또한 다시 코드를 뜯어보았을 때, 성능에는 크게 영향을 끼치지는 않겠지만 평균 혹은 단일 값을 반환하는 리스트 컴프리헨션 부분에서 조건문과 탐색 함수의 return은 굳이 필요 없다고 판단하여 코드를 수정했다.

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        l=[]
        self.level_search(root, l)
        l = [sum(i)/len(i) for i in l]
        return l

    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                if len(l) < level+1:
                    l.append([])
                l[level].append(node.val)
                if node.right:
                    queue.append((node.right, level+1))
                if node.left:
                    queue.append((node.left, level+1))