사칙연산 Python(SW Expert Academy)

난이도 : D4

문제번호 :1232

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다. 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다. 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라. 단, 중간 과정에서의 연산은 실수 연산으로 하되, 최종 결과값이 정수로 떨어지지 않으면 정수부만 출력한다. 위의 예에서는 최종 결과값이 13.5이므로 13을 출력하면 된다.

입력

각 테스트 케이스의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1≤N≤1000)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다. 정점이 단순한 수이면 정점번호와 해당 양의 정수가 주어지고, 정점이 연산자이면 정점번호, 연산자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호가 차례대로 주어진다. 정점번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점 번호를 매기는 특별한 규칙은 없으나, 루트 정점의 번호는 반드시 1이다. 입력에서 이웃한 수나 연산자는 모두 공백으로 구분된다. 위의 예시에서, 숫자 4가 7번 정점에 해당하면 “7 4”으로 주어지고, 연산자 ‘/’가 2번 정점에 해당하면 두 자식이 각각 숫자 9인 4번 정점과 연산자 ‘-’인 5번 정점이므로 “2 / 4 5”로 주어진다. 총 10개의 테스트 케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다. 답은 항상 정수값으로 기록한다.

예시

입력	출력
홈페이지 참조	홈페이지 참조

---

2. 문제풀이

메모이제이션과 비슷한 기법으로 풀 수 있습니다. 1번 노드부터 확인을 시작하는데 노드에 들어있는 값이 숫자가 아니라면 재귀를 이용하여 자식노드의 값을 가져옵니다. 물론 자식노드 또한 숫자가 아닐 수 있습니다. 그럴 경우 계속 밑으로 타고 내려가서 계산을 하게됩니다. 자식노드가 모두 숫자라면 자신이 가지고 있는 연산자를 통해 계산을 하고 자신의 위치에 연산된 값을 넣어줍니다. 트리구조여서 이해가 안되실 수 있습니다. 함수의 기능별로 분리를 해놨으니 분석을 통해 이해를 하실 수 있을것 같습니다.

---

3. 소스코드

# 1232 사칙연산 D4
 
def solution():
    N = int(input())
    node_connect_list = [[] for _ in range(N+1)]
    node_value_list = [0 for _ in range(N+1)]
    data_init(N, node_connect_list, node_value_list)
    return calculate_node(1, node_connect_list, node_value_list)
 
def data_init(N, node_connect_list, node_value_list):
    for _ in range(N):
        user_input = input().split()
        node_index = int(user_input[0])
        node_value = user_input[1]
        node_value_list[node_index] = node_value
        if len(user_input) != 2:
            node_connect_list[node_index].append(user_input[2])
            node_connect_list[node_index].append(user_input[3])
 
def calculate_node(idx, node_connect_list, node_value_list):
    if not len(node_connect_list[idx]):
        return node_value_list[idx]
 
    operator = node_value_list[idx]
    first_child_index = int(node_connect_list[idx][0])
    second_child_index = int(node_connect_list[idx][1])
 
    first_child_value = calculate_node(first_child_index, node_connect_list, node_value_list)
    second_child_value = calculate_node(second_child_index, node_connect_list, node_value_list)
 
    node_value_list[idx] = calulate(first_child_value, operator, second_child_value)
 
    return node_value_list[idx]
 
def calulate(value1, operator, value2):
    value1 = int(value1)
    value2 = int(value2)
    if operator == '+':
        return value1 + value2
    elif operator == '-':
        return value1 - value2
    elif operator == '*':
        return value1 * value2
    elif operator == '/':
        return value1 // value2
    print('error')
 
 
test_case = 10
for tc in range(test_case):
    answer = solution()
    print('#{} {}'.format(tc+1, answer))