import sys
sys.setrecursionlimit(10**3)
class Node:
def __init__(self, index, x, y):
self.index = index
self.x = x
self.y = y
self.left = None
self.right = None
class Tree:
def __init__(self, index, x, y):
self.head = Node(index, x, y)
def insert(self, index, x, y):
curr = self.head
while True:
if curr.x > x:
if curr.left == None:
curr.left = Node(index, x, y)
break
else:
curr = curr.left
else:
if curr.right == None:
curr.right = Node(index, x, y)
break
else:
curr = curr.right
def pre(self):
result = []
def do(curr):
result.append(curr.index)
if curr.left != None:
do(curr.left)
if curr.right != None:
do(curr.right)
do(self.head)
return result
def post(self):
result = []
def do(curr):
if curr.left != None:
do(curr.left)
if curr.right != None:
do(curr.right)
result.append(curr.index)
do(self.head)
return result
def solution(nodeinfo):
nodes = [[i+1, nodeinfo[i]] for i in range(len(nodeinfo))]
nodes.sort(key=lambda x: [-x[1][1], x[1][0]])
tree = Tree(nodes[0][0], nodes[0][1][0], nodes[0][1][1])
for node in nodes[1:]:
tree.insert(node[0], node[1][0], node[1][1])
pre = tree.pre()
post = tree.post()
answer = [pre, post]
return answer
2019 카카오 블라인드 - 5번
Node : index(해당 노드의 인덱스값), x(좌표), y(좌표), left(왼쪽자식), right(오른쪽자식)
Tree : 생성시 Node생성, insert(노드 추가), pre(전위순회), post(후위순회)
1. nodes를 nodeinfo의 인덱스와 좌표를 넣은 값으로 초기화
2. y좌표가 큰 순서, x좌표가 작은 순서로 정렬
3. 가장 초기값(최상위 노드)인 Tree클래스로 tree 정의
4. 초기 노드를 제외한 나머지를 tree에 insert해주면서 트리 만들기
- x 좌표가 작으면 왼쪽노드 크면 오른쪽노드
5. 전위 순회와 후위 순회 실시 (result 리스트 반환)
- 선방문
- 후방문
6. answer 출력
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] - 블록게임 (파이썬) (0) | 2022.02.15 |
---|---|
[프로그래머스] - 매칭점수 (파이썬) (0) | 2022.02.15 |
[프로그래머스] - 무지의 먹방 라이브 (파이썬) (0) | 2022.02.15 |
[프로그래머스] - 후보키 (파이썬) (0) | 2022.02.15 |
[프로그래머스] - 실패율 (파이썬) (0) | 2022.02.15 |