글 읽기 - 파이썬 maxheap을 구현 해 봤는데요. 어느 부분이 틀렸을까요?

gyjinro 3년 전 0

들어갈 때.. 나올 때 언제가 문제일까요?

일단 제공 된 예시는 통과 했습니다만, 제출에 넣으니 틀렸습니다. ㅠ

아니면 문제가 중복 키 값으로 인해 max_heap으로 하면 안되는걸까요?

import sys


class HeapNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value


class MaxHeap:
    def __init__(self):
        self.count = 0
        self.heap_array = [0,]

    def is_empty(self):
        return 1 if self.count == 0 else 0

    def insert_max_heap(self, key, value=0):
        self.heap_array.append(HeapNode(key, value))
        self.count += 1
        i = self.count
        while i != 1 and self.heap_array[i].key > self.heap_array[i//2].key:
            self.heap_array[i], self.heap_array[i//2] = self.heap_array[i//2], self.heap_array[i]
            i //= 2

    def pop_max_heap(self):
        if self.is_empty():
            print("fail to pop, heap is empty")
            return
        else:
            ret_nod = HeapNode(self.heap_array[1].key, self.heap_array[1].value)
            temp = HeapNode(self.heap_array[self.count].key, self.heap_array[self.count].value)
            self.count -= 1
            parent = 1
            child = 2
            while child <= self.count:
                if child < self.count and \
                        self.heap_array[child].key < self.heap_array[child+1].key:
                    child = child + 1
                if temp.key >= self.heap_array[child].key: break
                self.heap_array[parent].key = self.heap_array[child].key
                self.heap_array[parent].value = self.heap_array[child].value
                parent = child
                child = child * 2
            self.heap_array[parent].key = temp.key
            self.heap_array[parent].value = temp.value
            self.heap_array[self.count + 1] = 0
            return ret_nod

    def print_heap(self):
        if self.is_empty():
            print("heap is empty")
        else:
            for i in range(1, self.count + 1):
                print(f"{i}번째 노드의 key: {self.heap_array[i].key}, value:{self.heap_array[i].value}")

    def __len__(self):
        return self.count

tcc = int(sys.stdin.readline())
for _ in range(tcc):
    max_heap = MaxHeap()
    nc, pointer = map(int, sys.stdin.readline().split())
    pri_list = list(map(int, sys.stdin.readline().split()))
    for i in range(len(pri_list)):
        if i == pointer:
            max_heap.insert_max_heap(pri_list[i], 1)
        else:
            max_heap.insert_max_heap(pri_list[i])
    pop_counter = 0
    while 1:
        pop_counter += 1
        a = max_heap.pop_max_heap()
        if a.value == 1:
            break
    print(pop_counter)

yanghj1490 2년 전 0

최대 힙으로 뽑을 시

큐로 구현했을 때 뽑게 되는 순서와 차이가 발생합니다.

반례 드립니다.

#INPUT
1
6 3
1 1 9 1 1 1

#OUTPUT
4
#ANSWER
2

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

문제

문제

출처

ICPC

파이썬 maxheap을 구현 해 봤는데요. 어느 부분이 틀렸을까요?

gyjinro 3년 전 0

yanghj1490 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말