[Python] 26260번 이가 빠진 이진 트리

https://www.acmicpc.net/problem/26260

26260번: 이가 빠진 이진 트리

---

 

24/02/16

 

 

업다운 랜디를 하다가 만난 문제로, 처음 보고 뇌 정지가 와서 잘 해결하지 못했던 문제다.

 

이후 다시 풀게 되었고, 생각보다 간단한 해결 방법이 있어 글을 쓴다.

---

 

문제 접근 방식:

 

 

문제의 요구 조건은, 포화 이진 트리이면서 이진 검색 트리인 트리가 주어졌을 때, 특정 부분을 제거하고 다시 새롭게 썼을 때 바뀌는 트리의 후위 순회 결과를 출력하는 것이다.

 

처음에 보고 정석적으로 접근하는 문제인 줄 알고 많은 뇌절을 했다.

 

기존에 AVL트리를 짜둔 구현체가 생각나, 이를 불러와서 코드도 읽어보았다.

 

이 구현체를 사용해 트리에 원소 하나를 삭제하고 새로운 원소를 넣은 뒤, 후위 순회를 한 결과를 출력하도록 했다.

 

결과는 실패. 구체적인 실패 원인은 AVL트리를 잘못 짜둔 것이라고 추측한다.

 

난이도가 그렇게 높은 문제가 아니었기 때문에, 이렇게 복잡한 솔루션을 요구한다고 생각하지 않았고, 30분이 지난 이후에 태그를 까서 접근 방법을 잡아보려고 했다.

 

태그를 공개한 이후 바로 발견했던 것은, 결국 리스트를 정렬한 결과가 트리를 중위순회한 결과와 같다는 사실을 발견했다.

 

이를 알아차렸다면, 중위 순회를 후위 순회로 바꾸는 코드만 작성하면 된다.

 

중위 순회는 왼쪽 서브트리, 자기 자신, 오른쪽 서브트리 순으로 탐색을 진행하므로, 중위 순회를 한 결과에서 한 가운데는 자기 자신임을 곧바로 확인할 수 있다.

 

반면 후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 자기 자신 순으로 탐색을 진행하므로, 중위 순회를 한 결과에서 자기 자신만 제일 뒤로 보내기만 하면 된다.

 

따라서 각 결과를 왼쪽, 중간, 오른쪽으로 분할하여 더 이상 분할할 수 없을 때까지 분할한 뒤, 재귀적으로 다시 합치면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 26260번 이가 빠진 이진 트리
# 트리, 정렬
import sys
input = sys.stdin.readline

def inorder_to_postorder(li):
    if len(li) == 1:
        print(li[0], end = ' ')
        return
    mid = len(li)//2
    left = li[:mid]
    right = li[mid+1:]
    inorder_to_postorder(left)
    inorder_to_postorder(right)
    print(li[mid], end = ' ')
    return

N = int(input())
tree = list(map(int, input().rstrip().split()))
num = int(input())

for i in range(N):
    if tree[i] == -1:
        tree[i] = num
tree.sort()  # 트리를 중위 순회한 결과
inorder_to_postorder(tree)