이진힙 Python(SW Expert Academy)

난이도 : D2

문제번호 :5177

문제 주소 및 출처입니다.

swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

이진 최소힙은 다음과 같은 특징을 가진다.     - 항상 완전 이진 트리를 유지하기 위해 마지막 노드 뒤에 새 노드를 추가한다.     - 부모 노드의 값<자식 노드의 값을 유지한다. 새로 추가된 노드의 값이 조건에 맞지 않는 경우, 조건을 만족할 때까지 부모 노드와 값을 바꾼다.     - 노드 번호는 루트가 1번, 왼쪽에서 오른쪽으로, 더 이상 오른쪽이 없는 경우 다음 줄로 1씩 증가한다. 예를 들어 7, 2, 5, 3, 4, 6이 차례로 입력되면 다음과 같은 트리가 구성된다. 이때 마지막 노드인 6번의 조상은 3번과 1번 노드이다. 1000000이하인 N개의 서로 다른 자연수가 주어지면 입력 순서대로 이진 최소힙에 저장하고, 마지막 노드의 조상 노드에 저장된 정수의 합을 알아내는 프로그램을 작성하시오.

입력

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

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 6 7 2 5 3 4 6 6 3 1 4 16 23 12 8 18 57 11 52 14 45 63 40	#1 7 #2 5 #3 65

---

2. 문제풀이

여러가지 삽질을 해서 풀었던 문제입니다. 별 생각없이 모든 값을 한번에 heapify 하니까 정답이 다르게 나오더라구요. 여기서 원하는 것은 값을 하나씩 넣고 지속적으로 heapify를 해서 원하는 구조를 만드는 것입니다. 예시로 예제 3번을 들겠습니다. 처음 18 이라는 노드가 추가됩니다. 다음에 57 이라는 노드가 들어옵니다. 그림은 아래와 같습니다. 처음 문제의 발생은 이후 11이 들어올때입니다. 11이 들어옴으로써 규칙이 깨지게 됩니다. 부모가 자식노드보다 작아야 함으로 11과 18을 바꿔줍니다. 52 역시 들어오면 부모가 더 크기때문에 바꿔줍니다. 14 역시 부모노드보다 작으므로 교체를 해줍니다. 45, 63은 이상없이 추가되게 됩니다. 마지막으로 추가되는 40입니다. 역시 부모보다 작으므로 교체를 해줍니다. 이것이 힙의 최종적인 모습이 되게됩니다. 만약 부모와 교체했는데 바뀐부모가 조상보다 작다면 또 바꾸는 작업이 필요합니다. 최종노드의 부모들의 합이 결과이기 때문에 계산을 해보면 최종노드는 57. 최종 노드들의 부모들은 40, 14, 11입니다. 따라서 최종 정답은 40 + 14 + 11 = 65

 

---

3. 소스코드

def insert_heap(data):
    heap.append(data)
    index = len(heap)-1
    while index > 1 and heap[index] < heap[index//2]:
        heap[index], heap[index//2] = heap[index//2], heap[index]
        index //= 2
 
def get_sum_heap():
    value = 0
    idx = N // 2
    while idx:
        value += heap[idx]
        idx //= 2
    return value
 
for t in range(int(input())):
    answer = 0
    N = int(input())
    user_input = list(map(int, input().split()))
    heap = [0]
    for data in user_input:
        insert_heap(data)
    answer = get_sum_heap()
    
    print('#{} {}'.format(t+1, answer))