글 읽기 - [python] 힙을 구현해서 돌리는데 왜 시간초과나는지 모르겠습니다 ㅜㅜ

krocd 1년 전 0

라이브러리 사용하지 않고 heapify 를 구현해봤는데

어디서 시간을 잡아먹히는 지 모르겠습니다 ㅜㅜ 고수님들 도와주세요

import sys
from collections import deque
## heapify
def heapify(input_list, index, maxSize):
  left_index = index*2 +1
  right_index = index*2 +2
  min_index = index
  if (maxSize > left_index and input_list[min_index] > input_list[left_index]):
    min_index = left_index
  if (maxSize > right_index and input_list[min_index] > input_list[right_index]):
    min_index = right_index
  if(index != min_index):
    input_list[min_index], input_list[index] = input_list[index], input_list[min_index]
    input_list = heapify(input_list, min_index, maxSize)
  return input_list


def heap(input_list):
  start_node_index = (len(input_list)//2) - 1
  maxSize = len(input_list)
  for index in range(start_node_index, -1, -1):
    input_list = heapify(input_list, index, maxSize)
  return input_list

def main():
  input_list = deque()
  input_count = int(sys.stdin.readline().strip())
  for _ in range(input_count):
    input_num = int(sys.stdin.readline().strip())
    if(input_num == 0):
      if(len(input_list) == 0):
        print(0)
      else:
        print(input_list.popleft())
        heap(input_list)

    else:
      input_list.append(input_num)
      input_list = heap(input_list)



## 메인 입출력
if __name__ == "__main__":
  main()

zenith82114 1년 전 0

deque에서 하나씩 popleft 할 때마다 힙을 새로 만드시는 것 같은데 맞나요?

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

문제

문제

출처

ICPC

[python] 힙을 구현해서 돌리는데 왜 시간초과나는지 모르겠습니다 ㅜㅜ

krocd 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말