[프로그래머스 lv3]길 찾기 게임

문제설명

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

참고 

문제 해결 방법

 

주어진 리스트로 트리 만드는 부분 구현후, 스택을 활용해 트리 순회하는 코드 작성함 

후위 순회는 방문 여부를 체크 하도록 하여 구현하였음

코드 구현

 

 

def solution(nodeinfo):
    answer = []
    original = nodeinfo
    
    cnt = 0
    for i in nodeinfo:
        cnt +=1
        i.append(cnt)
    
    
    nodeinfo.sort(key = lambda x : (-x[1], x[0]))
    

    class Node:
        def __init__(self, key):
            self.left = None
            self.right = None
            self.val = key[2]
            self.x = key[0]
    
    class BST:
        def __init__(self):
            self.root = None
        
        def insert(self, key):
            if not self.root:
                self.root = Node(key)
            else:
                curr = self.root
                while 1:
                    if curr.x > key[0]:
                        if curr.left:
                            curr = curr.left
                        else:
                            curr.left = Node(key)
                            break
                    else:
                        if curr.right:
                            curr = curr.right
                        else:
                            curr.right = Node(key)
                            break
                    
        def preorder(self, result):
            curr = self.root
            stackk=[]
            stackk.append(curr)
            
            while 1:
                if len(stackk) != 0:
                    curr = stackk.pop()
                    
                    if curr is None:
                        continue
                    
                    result.append(curr.val)
                    stackk.append(curr.right)
                    stackk.append(curr.left)
                else:
                    break
            return result
                    
        def postorder(self, result):
            curr = self.root
            stackk=[(self.root, False)]
            # 이코드 대신 위에 코드 stackk.append(curr, False)
            
            while 1:
                if len(stackk) != 0:
                    curr, visited = stackk.pop()
                                      
                    if curr is None:
                        continue
                    if visited:
                        result.append(curr)
                    else:
                        stackk.append((curr.val, True))
                        stackk.append((curr.right, False))
                        stackk.append((curr.left, False))
                else:
                    break
            
            return result
    
    bst = BST()

    for key in nodeinfo:
        bst.insert(key)
        
    
    result = []
    answer.append(bst.preorder(result))
    result = []
    answer.append(bst.postorder(result))
    
    
    return answer

 

 

시간/공간 복잡도

 

O(N^2)

최적화 및 개선

 

하지않음

어려웠던 점

 

트리 구성 까지는 할 수 있는데, 트리 순회할때 재귀함수를 사용하지 않고 스택으로 구현하려니 어려웠다.