SWEA 1232 사칙연산 (파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 

SW Expert Academy

 

---

아이디어

1. 단말 노드들에는 숫자가 있다 단말 노드 부터 접근하여 그 부모가 가진 연산자를 사용하여 계산하자.
2. 후위 순회로 접근해야 될 것 같다. (틀림)

 

---

코드

def solve(v):
    for a, b, c, d in calc[::-1]:
        if b == '+':
            tree[int(a)] = tree[int(c)] + tree[int(d)]
        elif b == '-':
            tree[int(a)] = tree[int(c)] - tree[int(d)]
        elif b == '*':
            tree[int(a)] = tree[int(c)] * tree[int(d)]
        elif b == '/':
            tree[int(a)] = tree[int(c)] // tree[int(d)]

for tc in range(1, 11):
    N = int(input())
    tree = [0] * 1001
    tree_cal = [''] * 1001

    calc = []

    for n in range(N):
        n = input().split()
        if len(n) == 2:
            tree[int(n[0])] = int(n[1])
        else:
            calc.append(n)

    solve(1)
    print(f'#{tc}', tree[1])

 

---

후기 및 해설

• 이 문제는 트리의 갯수가 입력으로 들어오고, 트리의 갯수만큼 트리의 정보가 들어온다.
• 처음에는 node, v, *n으로 연산자가 들어오는 노드는 연산자의 리스트로 따로 만들어, 넣어 주고,
• 뒤의 *n은 무시하고 후위 순회로 진행했다.
• 하지만, 문제가 완전이진트리가 아닌 경우가 생기기 때문에 후위 순회로 접근하면 원하는 값이 나오지 않을 수 있다.
• 그래서 트리의 갯수 만큼 들어오는 정보를 리스트로 저장을 하고, 적절하게 조건을 넣어줘서 단말 노드에는 숫자를 넣어주고, 이 리스트 반복문으로 돌려서 적절하게 노드에 사칙연산한 값을 넣어준다.