이진 트리
임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 / 오른쪽 서브트리의 값을 사용하여 연산한다.
중간 과정에서 연산은 실수 연산으로, 최종 결과 값은 정수부만 출력
풀이 접근 방식
해당 노드의 값이 사칙연산 기호인지 확인
후위 탐색 과정으로 해도 되지 않을까?
# Pass!!
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
# 문제에서 주어진 트리는 루트 노드가 위치한 층 외에 한 층당 최소 2개의 노드가 필요하기 때문에(편향 X)
# 이런 방법이 가능한 듯
sorted(iterable, key=None, reverse=False)
iterable의 항목들로 새 정렬된 리스트를 리턴합니다.
key는 하나의 인자를 받는 함수, iterable의 각 요소들로부터 비교 키를 추출하는 데 사용
reverse는 정렬 방향을 결정합니다.
사칙연산을 수행하는 함수 정의 (operator
)
연산만을 위한 함수를 따로 정의하는 것이 코드를 나눠서 보는 데 도움이 될 것 같다.