프로그래머스 - 길 찾기 게임 본문
2019 카카오 블라인드 채용 문제이다.
레벨은 3이다.
https://school.programmers.co.kr/learn/courses/30/lessons/42892
문제에서 힌트? 인지는 모르겠지만 이진트리라고 말을 했다.
그래서 이진트리를 구현했다.
먼저 입력 값을 정렬을 해주었다.
첫 번째 값이 root값이 나온다.
그 root값을 기준으로 x좌표값을 비교하여 이진트리를 완성해 간다.
전위연산 후위연산은 재귀로 쉽게 구현할 수 있다.
import sys
sys.setrecursionlimit(10**6)
class node:
def __init__(self,item,y,x):
self.item = item
self.y = y # 얘는 필요가 없음
self.x = x
self.left = None
self.right = None
class BT():
def __init__(self, root = None):
self.root = root
def push(self, data):
ptr_Node = self.root
temp_node = self.root
while ptr_Node is not None:
temp_node = ptr_Node
if ptr_Node.x > data.x:
ptr_Node = ptr_Node.left
else:
ptr_Node = ptr_Node.right
if temp_node.x > data.x:
temp_node.left = data#주소값 참조
else:
temp_node.right = data
def preorder(self):
answer = []
def _preorder(node):
answer.append(node.item)
if node.left:
_preorder(node.left)
if node.right:
_preorder(node.right)
_preorder(self.root)
return answer
def postorder(self):
answer = []
def _postorder(node):
if node.left:
_postorder(node.left)
if node.right:
_postorder(node.right)
answer.append(node.item)
_postorder(self.root)
return answer
def solution(nodeinfo):
answer = []
sort_info = sorted(nodeinfo, key= lambda x : (-x[1],x[0]))
Tree = BT()
for idx, i in enumerate(sort_info):
data = node(nodeinfo.index(i)+1,i[1],i[0])
if idx == 0:
Tree.root = data
else:
Tree.push(data)
answer.append(Tree.preorder())
answer.append(Tree.postorder())
return answer
'알고리즘' 카테고리의 다른 글
백준 - 줄 세우기 (2252) (0) | 2023.12.27 |
---|---|
백준 - 부분수열의 합 2 (1208) (0) | 2023.12.27 |
백준 - 전깃줄 - 2(2568) (0) | 2023.12.12 |
백준 - 멀티탭 스케줄링(1700) (0) | 2023.12.12 |
백준 - 가장 긴 증가하는 부분 수열5(14003) (0) | 2023.12.12 |
Comments