SWEA_5117_이진 힙, SWEA_1232_사칙연산

SW Expert Academy

SWEA_5117_이진힙

 

문제

이진 최소힙은 다음과 같은 특징을 가진다.

    - 항상 완전 이진 트리를 유지하기 위해 마지막 노드 뒤에 새 노드를 추가한다.

    - 부모 노드의 값<자식 노드의 값을 유지한다. 새로 추가된 노드의 값이 조건에 맞지 않는 경우, 조건을 만족할 때까지 부모 노드와 값을 바꾼다.

    - 노드 번호는 루트가 1번, 왼쪽에서 오른쪽으로, 더 이상 오른쪽이 없는 경우 다음 줄로 1씩 증가한다.

예를 들어 7, 2, 5, 3, 4, 6이 차례로 입력되면 다음과 같은 트리가 구성된다.

이때 마지막 노드인 6번의 조상은 3번과 1번 노드이다.

1000000이하인 N개의 서로 다른 자연수가 주어지면 입력 순서대로 이진 최소힙에 저장하고, 마지막 노드의 조상 노드에 저장된 정수의 합을 알아내는 프로그램을 작성하시오.

 

 

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 N이 주어지고, 다음 줄에 1000000이하인 서로 다른 N개의 자연수가 주어진다. 5<=N<=500

 

 

 

코드

# import sys
# sys.stdin = open('5177_input.txt', 'r')

T = int(input())

def enq(n):
    global last
    last += 1
    heap[last] = n

    c = last
    p = c//2

    while p and heap[p] > heap[c]:
        heap[p], heap[c] = heap[c], heap[p]

        c = p
        p = c//2

def findRoot(N):
    sumV = 0
    while N//2 > 0:
        N = N//2
        sumV += heap[N]

    return sumV


for test_case in range(1, T+1):
    N = int(input())

    lst = list(map(int, input().split()))
    heap = [0] * 501
    last = 0

    for l in lst:
        enq(l)

    print(f'#{test_case} {findRoot(N)}')

 

 

 

 

 

SW Expert Academy

SWEA_1232_사칙연산

 

문제

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과에 해당 연산자를 적용한다.

 

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

계산 중간 과정에서의 연산은 모두 실수 연산으로 한다.

 

 

입력

총 10개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 N(1≤N≤1000)이 주어진다. 그다음 N 줄에 걸쳐 각 정점의 정보가 주어진다.

정점이 정수면 정점 번호와 양의 정수가 주어지고, 정점이 연산자이면 정점 번호, 연산자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점 번호가 차례대로 주어진다.

정점 번호는 1부터 N까지의 정수로 구분된고 루트 정점의 번호는 항상 1이다.

위의 예시에서, 숫자 4가 7번 정점에 해당하면 “7 4”으로 주어지고, 연산자 ‘/’가 2번 정점에 해당하면 두 자식이 각각 숫자 9인 4번 정점과 연산자 ‘-’인 5번 정점이므로 “2 / 4 5”로 주어진다.

 

 

출력

각 테스트케이스마다 '#t'(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 사칙연산을 계산한 결과값을 출력한다.

결과값은 소수점 아래는 버리고 정수로 출력한다.

 

 

코드

# import sys
# sys.stdin = open('1232_input.txt')

def postorder(n):
    global ST
    if tree[n]:
        postorder(left[n])
        postorder(right[n])
        if tree[n] in ['*', '/', '-', '+']:

            v1 = ST.pop()
            v2 = ST.pop()

            if tree[n] == '+':
                ST.append(v2 + v1)
            elif tree[n] == '-':
                ST.append(v2 - v1)
            elif tree[n] == '*':
                ST.append(v1 * v2)
            elif tree[n] == '/':
                ST.append(v2 / v1)
        else:
            ST.append(tree[n])


for test_case in range(1, 11):
    N = int(input())

    tree = [0] * (N+1)
    left = [0] * (N+1)
    right = [0] * (N+1)

    ST = []

    # 트리 생성
    for _ in range(N):
        lst = list(input().split())

        if lst[1].isdigit():
            tree[int(lst[0])] = int(lst[1])
        else:
            tree[int(lst[0])] = lst[1]
            left[int(lst[0])] = int(lst[2])
            right[int(lst[0])] = int(lst[3])

    postorder(1)

    print(f'#{test_case} {int(ST[0])}')

 

 

 

흔들리지 않고 얼른 제자리로 잘 돌아올 수 있는 사람이 되고 싶다.