링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42892
문제 설명
2차원 좌표값으로 이루어진 배열 nodeinfo를 인수로 준다.
좌표를 기준으로 아래와 같은 규칙으로 트리 노드들을 구성한다.
- 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
- 모든 노드는 서로 다른 x값을 가진다.
- 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
- 자식 노드의 y 값은 항상 부모 노드보다 작다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
위 과정을 통해 만들어진 이진트리를 가지고 전위 순회와 후위 순회를 한 결과를 return한다.
제한사항
- nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
- nodeinfo의 길이는 1 이상 10,000 이하이다.
- nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
- 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
- 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
- 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.
코드
import sys
sys.setrecursionlimit(10**6)
def solution(nodeinfo):
answer = [[],[]]
res = []
num = [i for i in range(1, len(nodeinfo)+1)]
world = [pair for pair in zip(num, nodeinfo)]
world.sort(key = lambda x: (-x[1][1], x[1][0]))
class Node:
def __init__(self, val, x, y):
self.val = val
self.x = x
self.y = y
self.left = None
self.right = None
def insert(self, val, x, y):
if x < self.x:
if self.left is None:
self.left = Node(val, x, y)
else:
self.left.insert(val, x, y)
elif x > self.x:
if self.right is None:
self.right = Node(val, x, y)
else:
self.right.insert(val, x, y)
def preorder(self):
answer[0].append(self.val)
if self.left:
self.left.preorder()
if self.right:
self.right.preorder()
def postorder(self):
if self.left:
self.left.postorder()
if self.right:
self.right.postorder()
answer[1].append(self.val)
root = Node(world[0][0], world[0][1][0],world[0][1][1])
world.pop(0)
for next in world:
root.insert(next[0], next[1][0], next[1][1])
root.preorder()
root.postorder()
return answer
아이디어
1. 들어온 순서가 노드에 값이니 zip()함수를 이용해 순서를 매겨준다.
2. nodeinfo의 y값이 트리의 레벨을 뜻하니, 가장 높은 y를 가진 노드가 루트노드. y의 내림차순으로 정렬을 해서 트리의 레벨별로 분류를 하고, x 값이 트리의 좌우측을 구분하니 x의 오름차순으로 정렬하면 좌에서 우 방향으로 노드를 정리한다.
3. 트리의 루트노드를 선정.
4. 트리에 노드를 x값을 기준으로 규칙에 맞게 좌,우측으로 넣어준다.
+@
* 바로바로 트리 구현이 안됐고 코드 작성이 중구난방한데, 나중에 따로 정리해서 팀노트..를 만들어 봐야겠다.
'알고리즘' 카테고리의 다른 글
프로그래머스 - 모두 0으로 만들기 (0) | 2022.12.19 |
---|---|
프로그래머스 - 오픈채팅방 (0) | 2022.12.17 |
백준(1644) - 소수의 연속합 (0) | 2022.12.12 |
프로그래머스 - 신고 결과 받기 (0) | 2022.12.07 |
프로그래머스 부대복귀 (0) | 2022.12.06 |