글 읽기 - 최소 힙을 Python 구현했는데 반례가 있을까요?

terra2007 1년 전 1

정말 반례가 없는 것 같은데 왜 틀렸는지 모르겠습니다 ㅠㅠ

from collections import deque
from sys import stdin
n=int(stdin.readline())

class priorityQueue():

    def __init__(self):
        self.heap = deque()
        self.count = 0

    def append(self, value):
        self.heap.append(value)
        index = self.count
        self.count += 1
        while(1):
            if(index == 0): break
            elif(self.heap[(index-1)//2] > self.heap[index]):
                temp = self.heap[index]
                self.heap[index] = self.heap[(index-1)//2]
                self.heap[(index-1)//2] = temp
                index = (index-1)//2
            else: break

    def pop(self):
        self.count -= 1
        print(self.heap.popleft())
        if(self.count != 0): self.heap.appendleft(self.heap.pop())
        index = 0
        while(1):
            child = index * 2 + 1
            if(self.count-1 > child and self.count >= 2 and self.heap[child] < self.heap[index] and self.heap[child] <= self.heap[child+1]):
                self.heap[child], self.heap[index] = self.heap[index], self.heap[child]
                index = child
            elif(self.count-1 > child+1 and self.count >= 3 and self.heap[child+1] < self.heap[index] and self.heap[child+1] <= self.heap[child]):
                self.heap[child+1], self.heap[index] = self.heap[index], self.heap[child+1]
                index = child + 1
            else: break
Q = priorityQueue()
for i in range(n):
    temp = int(stdin.readline())
    if(temp == 0 and len(Q.heap) == 0): print("0")
    elif(temp == 0): Q.pop()
    else: Q.append(temp)

dong5995 1년 전 1

반례 찾았습니다.

근데 굳이 heapq를 사용하지 않는 이유가 있으신가요?

#input
6
1
1    
2
0   
0
0

#output
1
2
1

#정답
1
1
2

terra2007 1년 전 0

한 번 구현 해보고 싶어서 구현 해봤습니다 ㅋㅋ

답변 감사합니다 !!

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

문제

문제

출처

ICPC

최소 힙을 Python 구현했는데 반례가 있을까요?

terra2007 1년 전 1

dong5995 1년 전 1

terra2007 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말