글 읽기 - [파이썬] 반례를 찾고 싶습니다!

chaem12 1년 전 0

이번 기회에 heap 다시 공부할겸 직접 구현해보려 했는데, 잘 안되네요. 반례를 찾고 싶습니다!

import sys
input = sys.stdin.readline

class Heap:
    def __init__(self):
        self.array = [0]
        self.length = 0
    def add(self, number):
        self.length+=1
        self.array.append(number)
        self.up_sort(self.length)
    def delete(self):
        if not self.length:
            print(0)
            return
        print(self.array[1])
        self.array[1] = self.array[self.length]
        self.length-=1
        self.down_sort(1)
    def down_sort(self, idx):
        if idx>=self.length or idx*2>self.length:
            return 
        min_index = idx*2
        if idx*2+1 <= self.length:
            min_index = idx*2+1 if self.array[idx*2]>self.array[idx*2+1] else idx*2
        if self.array[min_index] < self.array[idx]:
            self.array[min_index], self.array[idx] = self.array[idx], self.array[min_index]
            self.down_sort(min_index)
        else: 
            return 
    def up_sort(self, idx):
        if idx==1 or self.length == 1:
            return
        if self.array[idx]<self.array[idx//2]:
            self.array[idx], self.array[idx//2] = self.array[idx//2], self.array[idx]
            self.up_sort(idx//2)
        else:
            return 


# main
cnt = int(input())
heap = Heap()
for i in range(cnt):
    num = int(input())
    if(num!=0):
        heap.add(num)
    else:
        heap.delete()

dong5995 1년 전 0

반례입니다.

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

문제

문제

출처

ICPC

[파이썬] 반례를 찾고 싶습니다!

chaem12 1년 전 0

dong5995 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말