SWEA_1232_사칙연산

ByungHun Kim·2021년 4월 13일
0

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.

문제 링크

  • 이진 트리

  • 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 / 오른쪽 서브트리의 값을 사용하여 연산한다.

  • 중간 과정에서 연산은 실수 연산으로, 최종 결과 값은 정수부만 출력

문제를 보고 든 생각😌

  • 해당 노드의 값이 사칙연산 기호인지 숫자인지 확인해야겠다.

  • 노드의 키값을 읽는 방식은 후위 탐색으로 해도 되지 않을까?

통과한 코드😆

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)}")
  • 조건문에서 type을 사용할 때에는 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
  • 완전 이진 트리가 아닌 이진 트리에서 탐색을 하기 위해서는 left / right 배열과 같이 연결 관계를 나타내는 저장소가 필요하다.
  • 사칙 연산에 대한 계산을 좀 더 쉽게 할 수는 없을까??

다른 멋진 분들의 코드

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])}')
  • 딕셔너리로 접근하는 방식을 알아 소중한 시간이었다 ㅎㅎ
profile
Maker가 되고 싶은 개발자

0개의 댓글