글 읽기 - 파이썬 모듈 없이 구현해보려 했는데 어디가 틀린걸까요

lsj1137 2년 전 0

최소힙 문제입니다..

파이썬에 힙 모듈이 있다는 건 알았지만 직접 구현해보고 싶어서

만들어봤는데 어느 부분이 틀렸는지 모르겠습니다.

예제와 직접 입력해본 것들 중에는 틀린 게 없었습니다.

import sys
N = int(sys.stdin.readline().rstrip())
minheap = [0]
for _ in range(N):
  com = int(sys.stdin.readline().rstrip())
  if com==0:            #입력이 0일때
    if len(minheap)>1:    #최소힙 길이가 1보다 크면 (숫자가 하나라도 있을때)
      print(minheap[1])    #최솟값(인덱스1) 출력
      p, ch1, ch2 = 1,2,3
      while ch1<len(minheap):    #첫자식의 인덱스가 최소힙 길이보다 작을 동안
        if len(minheap)==ch2 or minheap[ch1]<minheap[ch2]:  #둘째자식의 인덱스가 힙의 길이와 같거나
                                                            #첫자식의 값이 더 작을때
          minheap[p] = minheap[ch1]            #부모자리에 첫자식 대입
          p = ch1
        else:
          minheap[p] = minheap[ch2]            #부모자리에 둘째자식 대입
          p = ch2
        ch1 = p*2                              #첫자식은 부모*2
        ch2 = p*2+1                            #둘째자식은 부모*2+1
      minheap.pop(ch1//2)
    else:                        #최소힙에 아무것도 없을때
      print(0)
  else:                  #입력이 0이 아닐때
    minheap.append(com)   #힙에 추가
  ch,par = len(minheap)-1,(len(minheap)-1)//2    #자식은 맨뒤 인덱스, 부모는 그거에 //2
  while minheap[ch]<minheap[par]:           #자식이 부모보다 작으면
    temp = minheap[par]                     #둘이 바꿈
    minheap[par] = minheap[ch]
    minheap[ch] = temp
    ch = par              #대를 거슬러 올라감
    par = ch//2 

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

문제

문제

출처

ICPC

파이썬 모듈 없이 구현해보려 했는데 어디가 틀린걸까요

lsj1137 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말