[Python] SWEA 5177 이진 힙

SW Expert Academy SWEA 5177 이진 힙 문제는 N개의 서로 다른 자연수를 입력 순서대로 이진 최소 힙에 저장하고, 마지막 노드의 조상 노드에 저장된 정수의 합을 알아내는 문제이다. binary tree 이진트리, heap 힙 자료구조에 관한 문제로 난이도는 D2다.

 

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

 

SW Expert Academy 5177 이진 힙 문제 정보

자료구조 분류

- tree 트리, binary tree 이진트리, heap 힙

난이도

- D2

 

이진 힙 문제 요약

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

 

문제 풀이 과정

1. 노드의 값, 번호, 왼쪽 자식, 오른쪽 자식, 다음 번호 노드 정보를 갖는 노드 클래스를 정의한다.
2. 연결 리스트에 일단 마지막 노드 뒤에 새 노드를 삽입하고, 이진 최소 힙의 특징에 맞게 노드의 자리를 조정한다.
3. 노드 삽입이 끝나면 마지막 노드의 조상 노드들을 찾아 정수의 합을 구한다.
4. 테스트 케이스 번호, 조상 노드에 저장된 정수의 합을 출력한다.

 

코드 및 설명

class Node(object):
    def __init__(self, data, num, left=None, right=None, next=None):
        self.data = data  # 노드의 값
        self.num = num  # 노드 번호
        self.left = left  # 노드의 왼쪽 자식
        self.right = right  # 노드의 오른쪽 자식
        self.next = next  # 노드의 다음 번호 노드


class LinkedList(object):
    cnt = 0  # 노드 번호
    sum = 0  # 조상 노드의 합

    def __init__(self):
        self.head = None

    # 연결 리스트가 비었는지 여부
    def is_empty(self):
        return not bool(self.head)

    # 노드 삽입
    def insert(self, value):
        LinkedList.cnt += 1
        # 비었다면 루트 노드로 저장
        if self.is_empty():
            self.head = Node(value, LinkedList.cnt)
        else:
            # 새 노드 생성 및 삽입
            new_node = Node(value, LinkedList.cnt)
            # 마지막 노드에 뒤에 저장
            last = self.find_last()  # 마지막 노드 찾기
            last.next = new_node
            # 부모 찾기
            parent = self.find_parent(LinkedList.cnt)
            # 노드 번호가 짝수면 왼쪽, 홀수면 오른쪽 자식 노드
            if LinkedList.cnt % 2 == 0:
                parent.left = new_node
            else:
                parent.right = new_node
            # 이진 최소힙 조건 검사
            self.condition_check(parent, new_node)

    # 이진 최소힙 조건 검사
    def condition_check(self, parent, child):
        # 부모 값이 자식 값보다 크면 바꾸기
        if parent.data > child.data:
            parent.data, child.data = child.data, parent.data
            # 부모가 루트 노드가 아니면 조건 검사 반복
            if parent.num != 1:
                grand_parent = self.find_parent(parent.num)
                self.condition_check(grand_parent, parent)

    # 부모 찾기
    def find_parent(self, child_num):
        parent = self.head
        while parent.num != child_num // 2:
            parent = parent.next
        return parent

    # 마지막 노드 찾기
    def find_last(self):
        last = self.head
        while last.next is not None:
            last = last.next
        return last

    # 마지막 노드의 조상 노드의 합 구하기
    def result(self, last=None):
        if last is None:
            last = self.find_last()

        parent = self.find_parent(last.num)
        LinkedList.sum += parent.data

        # 부모가 루트 노드가 아니면
        if parent.num != 1:
            self.result(parent)
        else:
            return LinkedList.sum


for tc in range(int(input())):
    N = int(input())

    nodes = list(input().split())
    tree = LinkedList()

    for n in nodes:
        tree.insert(int(n))

    LinkedList.cnt = 0
    LinkedList.sum = 0

    tree.result()
    print("#%d %d" % (tc + 1, LinkedList.sum))

---

주의할 점은 tree에 값을 삽입할 때 정수로 넣어야 한다. 문자열로 넣는다면, 4와 16을 비교했을 때 4가 더 크다고 여겨 자리가 바뀌어 버리는 오류가 발생한다.

 

SW Expert Academy SWEA 5177 이진 힙 문제는 binary tree 이진트리, heap 힙, 이진 최소 힙 자료구조 활용 문제이며 파이썬으로 구현하였다. 난이도는 D2이다.