글 읽기 - [Python] 최소힙, 최대힙은 맞았는데 어느부분이 문제일까요?

flame623 3년 전 0

밑에 똑같이 50%에서 틀렸습니다 나오는 분의 질문을 보니 삭제 후 재정렬할때 문제인것같던데 그쪽부분은 확인해봐도 문제가 없는것 같습니다... 반례가 뭐가 있을까요?

import sys
L = [0]
n = int(input())

def upheap(n, index):
    if index//2 != 0:
        if n[1] < L[index//2][1]:
            L[index] = L[index//2]
            L[index//2] = n
            upheap(n, index//2)
        elif n[1] == L[index//2][1]:
            if n[0] < L[index//2][0]:
                L[index] = L[index//2]
                L[index//2] = n
                upheap(n, index//2)
    else:
        L[index] = n

def downheap(n, index):
    m = 0
    s = 0
    if len(L)-1:
        L[index] = n
        for i in range(2*index, min(len(L), 2*index+2)):
            if n[1] - L[i][1] > s:
                s = n[1] - L[i][1]
                m = i
        if s != 0:
            if len(L) > 2*index+1 and L[2*index][1] == L[2*index+1][1]:
                m = index*2 if L[index*2][0] < L[index*2+1][0] else index*2+1
            L[index] = L[m]
            L[m] = n
            downheap(n, m)
        
for i in range(n):
    cal = int(sys.stdin.readline())
    if cal != 0:
        L.append([cal,abs(cal)])
        upheap([cal,abs(cal)], len(L)-1)
    elif len(L)-1:
        print(L[1][0])
        downheap(L.pop(-1), 1)
        print(L)
    else:
        print(0)

flame623 3년 전 0

28번째 라인에서 절댓값이 같은 수들을 재정렬할수가 없었네요. s를 다른 값으로 초기화하니 해결되었습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python] 최소힙, 최대힙은 맞았는데 어느부분이 문제일까요?

flame623 3년 전 0

flame623 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말