백준 1991 트리순회 실버1

문제 설명

• 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

 

 

입력값

1. 노드의 개수 N
2. 노드 왼쪽자식노드 오른쪽자식노드

• 노드가 없는 경우 '.'
• 루트노드는 항상 A

 

 

출력값

1. 전위 순회
2. 중위 순회
3. 후위 순회

 

 

풀이 1

# 108384KB, 88ms(PyPy3)

N = int(input())


# 자식 노드 저장
l = [0] * (N+1)       # 왼쪽
r = [0] * (N+1)       # 오른쪽

# 영어 딕셔너리
eng_to_num = {
  '.' : 0, 'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6,
  'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12,
  'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18,
  'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}


num_to_eng = {value : key for key, value in eng_to_num.items()}

for _ in range(N) :
  parents, left, right = input().split()
  l[eng_to_num[parents]] = eng_to_num[left]
  r[eng_to_num[parents]] = eng_to_num[right]


preorder = []
inorder = []
postorder = []


def order(T) : 
  if T :
    preorder.append(num_to_eng[T])
    order(l[T])
    inorder.append(num_to_eng[T])
    order(r[T])
    postorder.append(num_to_eng[T])


order(1)


print(''.join(preorder))
print(''.join(inorder))
print(''.join(postorder))

 

 

- 처음엔 알파벳 값을 인덱스를 사용하기 위해 알파벳을 숫자로 바꿔주는 딕셔너리를 만들었다

- 정답 출력을 위해선 숫자를 또 알파벳으로 바꿔야했기 때문에 key와 value 값을 바꿔 num_to_eng 딕셔너리도 만들었다

 

- 알파벳 -> 숫자 -> 알파벳 과정을 거쳐 정답 출력

- 메모리와 속도 면에서 크게 문제는 없으나 딕셔너리를 직접 입력하는 것도 힘들고, 불필요한 값 변환 과정, 인덱싱이 들어가서 효율적인 코드라 보긴 어렵다

 

 

풀이 2

 

# 108384KB, 84ms

N = int(input())
arr = dict()

for _ in range(N) :
  p,l,r = input().split()
  arr[p] = [l,r]

pre_order = ''
in_order=''
post_order=''


def order(T) :
    global pre_order, in_order, post_order
    
    if T == '.' :
        return
    
    pre_order += T
    order(arr[T][0])
    in_order += T
    order(arr[T][1])
    post_order += T

order('A')

print(pre_order)
print(in_order)
print(post_order)

 

 

- 그래서 처음 값을 받을 때 `arr = {부모 : [왼쪽 자식, 오른쪽 자식]}` 으로 받았다

- 그래서 왼쪽 자식 찾을 땐  `arr[부모][왼쪽자식]` 오른쪽 자식 찾을 땐 `arr[부모][오른쪽자식]`으로 찾았다

 

 

 

- arr을 실제 출력해보면 아래와 같다

 

 

- 시간은 4ms 줄어서 유의미하다고 보긴 어렵지만 풀이1보다 훨씬 더 효율적이고 코드도 짧고 간단하다.