[카카오공채] 2019 공채 5번 : 길 찾기 게임

카카오 2019 공채 5번 : 길 찾기 게임

주어진 규칙에 따라 이진트리를 만들고 순회하며 출력하는 문제

문제는 아래와 같이 흩뿌려진 노드를 이진트리로 만들고 전위순회, 후위순회를 하면서 풀면 되는 문제입니다.

풀이

이 문제를 보고 먼저 두단계로 나뉜다고 생각했습니다.
1. 이진트리를 잇고
2. 이진트리를 출력한다

그 중 문제는 1번.. 어떻게 저 흩뿌려진 노드로 트리를 만들 것인가! 이 문제의 핵심이 아닌가 합니다.

규칙은 아래와 같습니다

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

여기서 같은 레벨이면 y좌표가 같아야하니 루트노드인 7의 양옆에 자식노드가 있다면 두개의 y좌표는 같아야할 것입니다. 둘의 y좌표가 다른 그런 경우는 주어지지 않는다는 것이죠. 그리고 x좌표는 모두 다른 값을 가집니다. 즉 유니크한 값을 갖기때문에 뭔가 문제에서 써먹을 수 있을 것 같습니다.

제가 생각한 로직은 아래와 같습니다
1. 루트노드를 찾는다 : y좌표를 기준으로 내림차순정렬한 뒤 맨 앞 좌표
2. 루트노드부터 하나씩 자식노드를 붙여간다

• 왼쪽자식: 0 ~ 루트노드이 x좌표사이의 x좌표를 갖는 노드 중 y좌표가 가장 큰 노드
• 오른쪽자식: 루트노드이 x좌표 ~ 14사이의 x좌표를 갖는 노드 중 y좌표가 가장 큰 노드
  이때 x좌표 범위에 해당하는 노드들은 이분탐색으로 범위를 찾아준다

일반화를 하면 그림은 아래와 같습니다.
7은 x좌표가 0-8-14
4는 x좌표가 0-3-8
6은 x좌표가 0-1-3
으로 쪼개집니다. 이는 부모노드의 범위가 자식노드에게 영향을 주는 것을 알 수 있습니다.

저는 시간을 줄여주고자 범위를 추리는 것은 이분탐색을 사용했습니다.
x좌표가 하나씩 있다는 것을 고려해 x좌표만 뽑아서 정렬한뒤에 이분탐색으로 각각 시작과 끝 범위의 인덱스를 찾아주면 그것이 좌표를 x좌표로 정렬한 것에서의 범위와 같습니다.

그리고 level별로 진행을 하고자 BFS로 구현했습니다.

전체코드

import collections
import bisect
import sys

sys.setrecursionlimit(100000)


class Node:
    def __init__(self, val=0, xy=None, left=None, right=None):
        self.val = val
        self.xy = xy
        self.left = left
        self.right = right


def solution(nodeinfo):
    root = sorted(nodeinfo, key=lambda x: (-x[1], x[0]))[0]
    sortedInf = sorted(nodeinfo)
    sx = [n[0] for n in sortedInf]

    # 트리잇기
    queue = collections.deque()
    root = Node(nodeinfo.index(root) + 1, root)
    queue.append([-1, 100001, root])

    while queue:
        left, right, node = queue.popleft()
        # 왼쪽자식
        ll = bisect.bisect_right(sx, left)
        lr = bisect.bisect_left(sx, node.xy[0])
        if ll < lr:
            ln = sorted(sortedInf[ll:lr], key=lambda x: -x[1])[0]
            ln = Node(nodeinfo.index(ln) + 1, ln)
            node.left = ln
            queue.append([left, node.xy[0], ln])
        # 오른쪽자식
        rl = bisect.bisect_right(sx, node.xy[0])
        rr = bisect.bisect_left(sx, right)
        if rl < rr:
            rn = sorted(sortedInf[rl:rr], key=lambda x: -x[1])[0]
            rn = Node(nodeinfo.index(rn) + 1, rn)
            node.right = rn
            queue.append([node.xy[0], right, rn])

    # 트리출력
    result1 = []
    result2 = []

    def pre(node):
        if not node:
            return
        result1.append(node.val)
        pre(node.left)
        pre(node.right)

    def pro(node):
        if not node:
            return
        pro(node.left)
        pro(node.right)
        result2.append(node.val)

    pre(root)
    pro(root)
    answer = []
    answer.append(result1)
    answer.append(result2)

    return answer

문제푸는 과정에서 겪었던 두가지 런타임 오류
1. 이진트리를 배열로 구현하면 메모리초과가 일어납니다. -> 깊이가 최대 1000이기때문입니다
2. 재귀제한을 풀어주지 않으면 순회시에 최대재귀깊이가 초과합니다.