-2019 KAKAO BLIND RECRUITMENT.-
라 전무님이 또 일을 벌였습니다.
트리 문제입니다. 주어진 좌표를 가지고 트리를 잘 만드는 것이 관건일 것 같습니다.
좌표의 순서가 랜덤이기 때문에 먼저 정렬을 해야할 듯 싶습니다.
먼저 아래 조건을 주목해 봅시다.
같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
즉 y좌표를 기준으로 내림차순 정렬하면, 트리의 Root가 될 좌표부터 시작해 bfs 형태를 갖는 배열을 얻게 됩니다.
처음 주어진 nodeinfo 배열을 정렬해봅시다.
그 전에 원래 순서가 바뀔 것을 대비해서 각 좌표(node)에 추가로 번호(순서)를 붙혀줍니다.
for i in range(len(nodeinfo)):
nodeinfo[i].append(i+1)
nodeinfo.sort(key=lambda x:(x[1], -x[0]), reverse=True)
y의 값을 기준으로 내림차순 정렬함과 동시에 같은 y값 안에서는 x값을 기준으로 오름차순 정렬 될 수 있도록 했습니다.
(- 부호를 붙이면 반대로 정렬됨을 이용)
이러면 좌표들의 순서는 한 level씩 이동하면서 동시에 왼쪽 -> 오른쪽 순서로 정렬이 되겠죠?
다음으로는 트리를 만들기 위해 파이썬의 dataclass 모듈을 사용해줍시다.
from dataclasses import dataclass
class tree:
value = None
leftchild = None
rightchild = None
def solution(nodeinfo):
node = tree()
문제에서 주어진 자료구조는 이진트리이므로 한 node는 각각 Left, Right에 자식을 갖습니다. (없을수도 있음)
가장 먼저 트리의 Root가 될 node를 만들어 줍니다.
node.value = nodeinfo[0]
node.leftchild = getchild([x for x in nodeinfo if x[0] < node.value[0]])
node.rightchild = getchild([x for x in nodeinfo if x[0] > node.value[0]])
y값을 기준으로 우선 정렬했기 때문에 nodeinfo의 인덱스 0번 값이 Root의 값이 됩니다.
leftchild Node와 rightchild Node는 재귀를 통해 가져오도록 하겠습니다.
이 때 함수의 인자로는 left의 경우 Root의 x값보다 작은 좌표값들의 묶음을, right의 경우엔 Root의 x값보다 큰 좌표값들의 묶음을 보내줍니다. 이는 우선 아래의 조건이 있기 때문에 생각해볼 수 있습니다.
임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
또한, Tree(혹은 subtree)의 Root level에 해당하는 노드는 언제나 Root가 유일하다고 볼 수 있습니다. 그것이 Tree이니까 따라서 기준 node를 제외한 나머지 node들은 무조건 level이 크다고 보장됩니다.
그러므로 저렇게 각 범위에 해당하는 좌표 묶음을 컴프리헨션을 이용해 만들어주어 인자로 보내줍니다.
이제 함수 부분으로 넘어가봅시다.
def getchild(nodeinfo):
if len(nodeinfo) == 0:
return None
new_node = tree()
new_node.value = nodeinfo[0]
new_node.leftchild = getchild([x for x in nodeinfo if x[0] < new_node.value[0]])
new_node.rightchild = getchild([x for x in nodeinfo if x[0] > new_node.value[0]])
return new_node
재귀가 진행되고 y값이 제일 작은, Leaf에 해당하는 좌표값에 도달할 경우엔 nodeinfo는 빈 배열이 될 것입니다. 다른 값들은 모두 사용되고 걸러졌으니까요. 당연히 child는 없기에 None을 반환해줍니다.
반대로 그렇지 않을 경우, nodeinfo가 존재할 경우는 child가 존재한다는 뜻입니다. main과 같이 새롭게 node를 만들어주고 각각의 child는 getchild 함수를 이용해 연결해줍니다. 이곳에서도 마찬가지로 자신의 자식들, 손자들은 항상 자신의 x값보다는 작거나 클 수 밖에 없으므로 똑같이 컴프리헨션을 이용해줍니다.
마지막으로는 새롭게 만들어진 node 자기 자신을 반환해줍니다. 반환된 node는 그대로 부모의 leftchild 혹은 rightchild와 연결될 것입니다.
재귀가 완료되면 트리가 완성됐습니다! 이후에는 트리를 전위 순회, 후위 순회 해주기만 하면 됩니다.
def preorder(node, array):
if node is None:
return
array.append(node.value[2])
preorder(node.leftchild, array)
preorder(node.rightchild, array)
def postorder(node, array):
if node is None:
return
postorder(node.leftchild, array)
postorder(node.rightchild, array)
array.append(node.value[2])
역시 재귀를 이용하는데, 전위 순회는 (출력-탐색-탐색) 의 순서를, 후위 순회는 (탐색-탐색-출력) 의 순서를 지키시면 편합니다.
저는 출력 단계를 answer 배열에 다이렉트하게 추가하는 식으로 구현했습니다.
(매개변수 array가 각각 answer[0], answer[1]에 해당합니다.)
무한히 재귀호출 되는것을 막기 위해 방지턱도 넣어줍니다.
출력할 때 맨 처음에 넣어놨었던 문제에서 제시한 각 node의 번호를 출력해주면 됩니다. (인덱스 2번)
이러면 깔끔하게 정답!
..일 줄 알았으나 제출하면 틀리는 테스트케이스가 있습니다.
재귀로 푸는 문제에서 런타임 에러가 나온다? 재귀 깊이 한계에 부딪혔을 가능성이 매우 높습니다.
아래 코드를 맨 위에 입력해줍시다.
import sys
sys.setrecursionlimit(1005)
제가 1000부터 해봤는데 1005번 부터 런타임 에러가 안뜹니다.
근데 분명 문제에서 최대 깊이 1000까지만 주어진다고 했는데 왜 1005번일까..
import sys
from dataclasses import dataclass
sys.setrecursionlimit(1005)
class tree:
value = None
leftchild = None
rightchild = None
def preorder(node, array):
if node is None:
return
array.append(node.value[2])
preorder(node.leftchild, array)
preorder(node.rightchild, array)
def postorder(node, array):
if node is None:
return
postorder(node.leftchild, array)
postorder(node.rightchild, array)
array.append(node.value[2])
def getchild(nodeinfo):
if len(nodeinfo) == 0:
return None
new_node = tree()
new_node.value = nodeinfo[0]
new_node.leftchild = getchild([x for x in nodeinfo if x[0] < new_node.value[0]])
new_node.rightchild = getchild([x for x in nodeinfo if x[0] > new_node.value[0]])
return new_node
def solution(nodeinfo):
answer = [[] for x in range(2)]
for i in range(len(nodeinfo)):
nodeinfo[i].append(i+1)
nodeinfo.sort(key=lambda x:(x[1], -x[0]), reverse=True)
node = tree()
node.value = nodeinfo[0]
node.leftchild = getchild([x for x in nodeinfo if x[0] < node.value[0]])
node.rightchild = getchild([x for x in nodeinfo if x[0] > node.value[0]])
preorder(node, answer[0])
postorder(node, answer[1])
return answer
※반박시 님 말이 다 맞음