[Programmers/프로그래머스] 2019 KAKAO BLIND RECRUITMENT [코딩테스트]

1. [Lv. 2] 오픈채팅방
2. [Lv. 1] 실패율
3. [Lv. 2] 후보키
4. [Lv. 4] 무지의 먹방 라이브
5. [Lv. 3] 길 찾기 게임
6. [Lv. 3] 매칭 점수
7. [Lv. 4] 블록 게임

📌 문제

📝 제한사항

💻 입출력 예

📖 입출력 예에 대한 설명

📌 풀이

def preorder(tree, root, result):
    result.append(root)         # 일단 방문했으므로 현재노드 저장하고
    if tree[root][2]:           # left노드 존재하면 방문
        result = preorder(tree, tree[root][2], result)
    if tree[root][3]:           # right노드 존재하면 방문
        result = preorder(tree, tree[root][3], result)
    return result

def postorder(tree, root, result):
    result.append(root)         # 일단 방문했으므로 현재노드 저장하고
    if tree[root][3]:           # right노드 존재하면 방문
        result = postorder(tree, tree[root][3], result)
    if tree[root][2]:           # left노드 존재하면 방문
        result = postorder(tree, tree[root][2], result)
    return result
        
def solution(nodeinfo):
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i + 1)
    
    # 트리 구조 생성
    tree_dict = {}
    nodeinfo = sorted(nodeinfo, key=lambda x:(-x[1], x[0]))
    for x, y, node in nodeinfo:
        tree_dict[node] = [x, y, None, None]    # [x, y, left, right]
        idx = nodeinfo[0][2]                    # 탐색노드 초기값 Root 노드
        while True:                             # 현재까지 생성된 트리에 대하여 현재노드가 위치할 자리 탐색
            if x < tree_dict[idx][0]:           # 현재노드 < 탐색노드이면 left노드 확인
                if tree_dict[idx][2] == None:   # left노드에 연결된 노드가 없다면
                    tree_dict[idx][2] = node    # left노드에 현재노드 연결
                    break                       # 트리 탐색 종료
                idx = tree_dict[idx][2]         # left노드에 연결된 노드가 있다면 탐색노드를 left노드로 갱신
            elif x > tree_dict[idx][0]:         # 현재노드 > 탐색노드이면 right노드 확인
                if tree_dict[idx][3] == None:   # right노드에 연결된 노드가 없다면
                    tree_dict[idx][3] = node    # right노드에 현재노드 연결
                    break                       # 트리 탐색 종료
                idx = tree_dict[idx][3]         # right노드에 연결된 노드가 있다면 탐색노드를 right노드로 갱신
            else:       # 현재노드 == 탐색노드이면
                break   # 이미 현재노드의 위치를 찾은것이므로 트리 탐색 종료
    
    answer_pre = preorder(tree_dict, nodeinfo[0][2], [])    # 왼쪽방향순회
    answer_post = postorder(tree_dict, nodeinfo[0][2], [])  # 오른쪽방향순회 역순
    
    return [answer_pre, answer_post[-1::-1]]