사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.
이진 트리
임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 / 오른쪽 서브트리의 값을 사용하여 연산한다.
중간 과정에서 연산은 실수 연산으로, 최종 결과 값은 정수부만 출력
해당 노드의 값이 사칙연산 기호인지 숫자인지 확인해야겠다.
노드의 키값을 읽는 방식은 후위 탐색으로 해도 되지 않을까?
def operator(num1, num2, oper):
if oper == "+":
return num1 + num2
elif oper == "-":
return num1 - num2
elif oper == "*":
return num1 * num2
else:
return num1 / num2
# 후위 탐색 과정
def postorder(node_idx):
if 1 <= node_idx <= N:
# 현재 노드의 값이 사칙연산이라면?
if type(tree[node_idx]) is str:
left_value = postorder(left[node_idx])
right_value = postorder(right[node_idx])
# 현재 노드의 키값을 연산자에서 결과값으로 변경
tree[node_idx] = operator(left_value, right_value, tree[node_idx])
return tree[node_idx]
# 10개의 테스트 케이스
for tc in range(1, 11):
# N: 노드의 개수
N = int(input())
# 값을 담을 tree 배열 정의
tree = [0] * (N + 1)
# 연결 관계를 담을 배열 정의 (완전 이진 트리가 아니므로)
left = [0] * (N + 1)
right = [0] * (N + 1)
# 트리 값 및 연결 관계 저장
for _ in range(N):
idx, value, *arg = input().split()
idx = int(idx)
if value in "+-*/":
left[idx] = int(arg[0])
right[idx] = int(arg[1])
else:
value = int(value)
tree[idx] = value
# 루트 노드 값 구하기
result = postorder(1)
print(f"#{tc} {int(result)}")
is
연산자를 사용해도 된다.if type(value) == str:
pass
if type(value) is str:
pass
==
연산자 (Equality)
비교 대상: 값(value)
is
연산자 (Identity)
비교 대상: (참조하는) 객체의 주소
l1 = [1, 2, 3]
l2 = [1, 2, 3]
l3 = l1
if l1 == l2:
print("==")
else:
print("!=")
if l1 is l2:
print("is")
else:
print("is not")
if l1 is l3:
print("is")
else:
print("is not")
# 출력값
==
is not
is
def operator(num1, num2, oper):
if oper == '-':
return num1 - num2
elif oper == '+':
return num1 + num2
elif oper == '*':
return num1 * num2
else:
return num1 / num2
for tc in range(1,11):
N = int(input())
depth = len(bin(N)) - 2
tree = [0] * (1<<depth)
command = {}
for _ in range(N):
x = list(input().split())
if len(x) == 4:
# 연산자는 딕셔너리에 담고
command[x[0]] = x[1:]
else:
# 숫자는 트리에 바로 담는다.
tree[int(x[0])] = int(x[1])
# key의 역순으로 정렬하여, 계산 진행 (멋지다..ㅠ)
for node in sorted(command.keys() , key = lambda x: int(x), reverse = True):
child1, child2 = tree[int(command[node][1])], tree[int(command[node][2])]
tree[int(node)] = operator(child1, child2, command[node][0])
print('#{} {}'.format(tc, int(tree[1])))
bin()
정수를 《0b》 가 앞에 붙은 이진 문자열로 변환합니다.
# 노드의 개수를 알고 있을 때, 트리의 높이를 구하는 방법
# N이 6일 때를 가정해보자.
>> bin(6)
>> "ob110"
# ob가 붙은 이진 문자열이기 때문에 실질적인 이진 문자열은 뒤에 3자리이다.
>> len(bin(6)) - 2
>> 3
sorted(iterable, key=None, reverse=False)
iterable의 항목들로 새 정렬된 리스트를 리턴합니다.
key는 하나의 인자를 받는 함수, iterable의 각 요소들로부터 비교 키를 추출하는 데 사용
reverse는 정렬 방향을 결정합니다.
사칙연산을 수행하는 함수 정의 (operator
)
연산만을 위한 함수를 따로 정의하는 것이 코드를 나눠서 보는 데 도움이 될 것 같다.
T = 10
for tc in range(1, T + 1):
N = int(input())
# index를 맞추기 위해 [0]을 0번 인덱스에 삽입
arr= [[0]]
tree = [None] * (N + 1)
for i in range(1, N + 1):
# 각 노드의 정보를 arr 배열에 저장
arr += [list(input().split())]
# 사칙연산이 아닌 경우, tree에 값을 바로 넣어준다.
if len(arr[i]) == 2:
tree[int(arr[i][0])] = int(arr[i][1])
# arr을 역순으로 탐색 (하위 tree에는 이미 숫자 값들이 존재하기에)
for i in range(N, 0, -1):
# 현재 살펴보고 있는 노드의 값이 사칙연산이라면, 값을 계산하여 tree에 저장
if len(arr[i]) != 2:
a0, a1, a2, a3 = int(arr[i][0]), arr[i][1], int(arr[i][2]), int(arr[i][3])
if a1 == '+':
tree[a0] = tree[a2] + tree[a3]
elif a1 == '-':
tree[a0] = tree[a2] - tree[a3]
elif a1 == '*':
tree[a0] = tree[a2] * tree[a3]
else:
tree[a0] = tree[a2] / tree[a3]
print('#{} {}'.format(tc, int(tree[1])))
T = 10
for test_case in range(1, T + 1):
N = int(input())
dic_c = {}
li_tree = [-1 for _ in range(N + 1)]
for i in range(N):
li_tmp = list(input().split())
# 사칙연산인 경우
if len(li_tmp) == 4:
node, op, c1, c2 = li_tmp
node, c1, c2 = int(node), int(c1), int(c2)
# 해당 노드의 인덱스를 key로 하고, 자식 노드의 인덱스를 튜플로 value에 저장
dic_c[node] = (c1,c2)
# 트리에 연산자를 저장
li_tree[node] = op
# 숫자인 경우
else:
node, value = li_tmp
node, value = int(node), int(value)
# 트리에 숫자를 저장
li_tree[node] = value
# 딕셔너리를 key의 역순(바닥부터 올라오도록)으로 정렬하여, 결과값을 트리에 저장
for i in sorted(dic_c.keys(), reverse=True):
if li_tree[i] == '+':
li_tree[i] = li_tree[dic_c[i][0]] + li_tree[dic_c[i][1]]
elif li_tree[i] == '-':
li_tree[i] = li_tree[dic_c[i][0]] - li_tree[dic_c[i][1]]
elif li_tree[i] == '*':
li_tree[i] = li_tree[dic_c[i][0]] * li_tree[dic_c[i][1]]
elif li_tree[i] == '/':
li_tree[i] = li_tree[dic_c[i][0]] // li_tree[dic_c[i][1]]
print(f'#{test_case} {int(li_tree[1])}')