SWEA 5177 이진 힙 (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

풀이

def push(item):
    global last
    last += 1
    h[last] = item

    c, p = last, last // 2
    while True:
        if p > 0 and h[c] < h[p]:
            h[c], h[p] = h[p], h[c]
            c = p
            p = c // 2
        else:
            break

def pop():
    ret = h[1]
    global last
    h[1] = h[last]
    last -= 1

    p, c = 1, 2

    while c <= last:
        if c + 1 <= last and h[c] > h[c+1]:
            c += 1

        if h[c] <= h[p]: break

        h[c], h[p] = h[p], h[c]
        p = c
        c = p*2

    return ret

for tc in range(int(input())):
    size = 1000
    h = [0] * size
    last = 0

    V = int(input())
    data = list(map(int, input().split()))

    for val in data:
        push(val)

    p_lst = []
    c = V
    while True:
        p = c // 2
        p_lst.append(h[p])
        c = p
        if p == 0:
            break
    print(f'#{tc+1}', sum(p_lst))

 

---

후기

• 이진 힙을 구현해보는 문제였다.
• 라이브러리를 사용하지 않고 직접 h와 last를 정해 push, pop 함수를 만들어 최소, 최대 힙을 구현했다.
• push는 비교적 간단하지만, pop은 push보다 조금 복잡하다. 
• 또한, p와 c를 바꿔주는 게 좀 아직 헷갈린다.