일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 전산기초
- 이것이 코딩테스트다 with 파이썬
- CS231n
- ssd
- STL
- 실전알고리즘
- 프로그래머스
- ubuntu
- 2단계
- 자료구조 및 실습
- pytorch
- test-helper
- 구현
- docker
- SWEA
- 딥러닝
- 머신러닝
- 1단계
- MySQL
- Python
- AWS
- C++
- Object detection
- 코드수행
- 3단계
- 파이썬
- 백준
- 모두를 위한 딥러닝 강좌 시즌1
- 그리디
- cs
- Today
- Total
곰퓨타의 SW 이야기
[프로그래머스 level3 길 찾기 게임] 이진 트리 및 전위순회, 후위순회 구현하기! 본문
해결해야하는 문제는 다음과 같았다.
https://programmers.co.kr/learn/courses/30/lessons/42892
코딩테스트 연습 - 길 찾기 게임
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]
programmers.co.kr
우선 이 문제를 해결하기 위해서는 이진트리 및 전위순회 후위순회를 알아야할 것 같았다.
기본 개념은 다음과 같다.
이진트리
각각의 노드가 최 대 두 개의 자식 노드를 가지는 트리 자료 구조이다.
이진 탐색 트리
이진 탐색의 효율성을 유지하면서 빈번한 자료의 입력과 삭제가 가능하도록 한ㄷ나.
- 각 노드의 왼쪽 서브트리는 해당 노드 값보다 작은 값을 가진 노드로 이루어져있다.
- 각 노드의 오른쪽 서브트리는 해당 노드 값보다 큰 값을 가진 노드로 이루어져있다.
- 중복되는 노드가 없다.
-> 왼쪽은 현재 값보다 작다, 오른쪽은 현재값보다 크다를 통해 빠르게 search 가 가능하다.
preorder (Dfs 같은듯!)
root -> left -> right 순서로 순회한다.
F -> B -> A -> D -> C -> E -> G -> I -> H
postorder
left -> right -> root 순서로 순회한다.
A -> C -> E -> D -> B -> H -> I -> G -> F
cf ) inorder
left->root -> right 순서로 순회한다.
A -> B -> C -> D -> E -> F -> G -> H -> I
구현은 다음과 같이 하였다.
아이디어를 바탕으로 작성한 코드는 다음과 같다.
class Node():
def __init__(self,idx,x,y):
self.idx = idx
self.x = x
self.y = y
self.left = self.right = None
class BT():
def __init__(self):
self.root = None
self.preorder_arr = []
self.postorder_arr = []
def insert(self,idx,x,y):
if self.root is None :
self.root = Node(idx,x,y)
return
self.current = self.root
while True :
if x < self.current.x :
if self.current.left != None :
self.current = self.current.left
else :
self.current.left = Node(idx,x,y)
break
else :
if self.current.right != None :
self.current = self.current.right
else :
self.current.right = Node(idx,x,y)
break
def preorder(self,node):
if node != None :
self.preorder_arr.append(node.idx)
if node.left :
self.preorder(node.left)
if node.right :
self.preorder(node.right)
def postorder(self,node):
if node != None :
if node.left :
self.postorder(node.left)
if node.right :
self.postorder(node.right)
self.postorder_arr.append(node.idx)
def solution(nodeinfo):
answer = []
binary_tree = BT()
newnodeinfo = []
for idx, value in enumerate(nodeinfo) :
newnodeinfo.append([idx+1,value[0], value[1]])
newnodeinfo.sort(key=lambda x : x[2],reverse=True)
for idx, tx,ty in newnodeinfo :
binary_tree.insert(idx,tx, ty)
binary_tree.preorder(binary_tree.root)
binary_tree.postorder(binary_tree.root)
answer.append(binary_tree.preorder_arr)
answer.append(binary_tree.postorder_arr)
return answer
하지만 이는 6,7 번 테스트케이스에서 런타임 에러가 난다.
질문하기에 똑같은 고민을 하는 분이 있어, 확인해본 결과
재귀함수 호출 횟수 제한 때문이었다.
이는 다음과 같은 코드를 통해 제한 횟수를 늘려주었다.
import sys
sys.setrecursionlimit(10**6)
이를 추가한 최종 코드는 다음과 같다.
import sys
sys.setrecursionlimit(10**6)
class Node():
def __init__(self,idx,x,y):
self.idx = idx
self.x = x
self.y = y
self.left = self.right = None
class BT():
def __init__(self):
self.root = None
self.preorder_arr = []
self.postorder_arr = []
def insert(self,idx,x,y):
if self.root is None :
self.root = Node(idx,x,y)
return
self.current = self.root
while True :
if x < self.current.x :
if self.current.left != None :
self.current = self.current.left
else :
self.current.left = Node(idx,x,y)
break
else :
if self.current.right != None :
self.current = self.current.right
else :
self.current.right = Node(idx,x,y)
break
def preorder(self,node):
if node != None :
self.preorder_arr.append(node.idx)
if node.left :
self.preorder(node.left)
if node.right :
self.preorder(node.right)
def postorder(self,node):
if node != None :
if node.left :
self.postorder(node.left)
if node.right :
self.postorder(node.right)
self.postorder_arr.append(node.idx)
def solution(nodeinfo):
answer = []
binary_tree = BT()
newnodeinfo = []
for idx, value in enumerate(nodeinfo) :
newnodeinfo.append([idx+1,value[0], value[1]])
newnodeinfo.sort(key=lambda x : x[2],reverse=True)
for idx, tx,ty in newnodeinfo :
binary_tree.insert(idx,tx, ty)
binary_tree.preorder(binary_tree.root)
binary_tree.postorder(binary_tree.root)
answer.append(binary_tree.preorder_arr)
answer.append(binary_tree.postorder_arr)
return answer
'TIL > 프로그래머스' 카테고리의 다른 글
[프로그래머스 level3 경주로 건설] bfs 활용하기 (0) | 2021.09.10 |
---|---|
[프로그래머스 level3 광고 삽입] 다이나믹 프로그래밍 활용하기 (0) | 2021.09.10 |
[프로그래머스 level3 합승 택시 요금] 최단 경로 구하기(ft. 다익스트라, 플로이드 워셜) (0) | 2021.09.07 |
[프로그래머스 level3 불량 사용자] dictionary와 dfs 활용하기 (0) | 2021.09.05 |
[프로그래머스 level3 여행경로] bfs/dfs 활용하기 (0) | 2021.09.03 |