글 읽기 - 힙 구조 문제 시간 초과가 뜹니다

bomul1128 2년 전 1

제 나름대로 시간복잡도를 고려해서 한다고 코드를 작성하였는데 시간 초과가 뜨네요

혹시 try 문을 이중으로 쓴 것이 코드 처리 속도에 영향을 많이 주었을까요?

아니면 다른 원인이 있을까요??

# max heap 생성
def making_heap(heap, new_num):
    index = len(heap)
    heap.append(new_num)
    while True:
        if heap [index] > heap [index // 2] > 0:
            heap [index], heap [index // 2] = heap [index // 2], heap [index]
            index = index // 2
        else:
            break
    return heap

# max heap 꼭대기 원소 제거
def reorder_heap(heap):
    index = 1
    if len(heap) > 2:
        heap [index] = heap.pop()
    else:
        heap = [0]
    while True:
        try: # 비교 대상에 가지가 2개 달려 있을 때
            if heap [index * 2] > heap [index] and heap [index * 2] >= heap [index * 2 + 1]:
                heap [index], heap [index * 2] = heap [index * 2], heap [index]
                index = index * 2
            elif heap [index * 2 + 1] > heap [index] and heap [index * 2 + 1] > heap [index * 2]:
                heap [index], heap [index * 2 + 1] = heap [index * 2 + 1], heap [index]
                index = index * 2 + 1
            else:
                break
        except:
            try: # 비교 대상에 가지가 1개 달려 있을 때
                if heap [index * 2] > heap [index]:
                    heap [index], heap [index * 2] = heap [index * 2], heap [index]
                    index = index * 2
                else:
                    break
            except: # 비교 대상이 없을 때 (가지의 마지막 원소일 때)
                break
    return heap

# 초기값 설정
N = int(input())
my_heap = [0]

# 문제 해결
for _ in range(N):
    my_input = int(input())
    if my_input == 0:
        if len(my_heap) == 1:
            print(0)
        else:
            print(my_heap[1])
            my_heap = reorder_heap(my_heap)
    else:
        my_heap = making_heap(my_heap, my_input)

seho27060 2년 전 1

저도 구현해봤는데, 계속 시간초과나서 궁금합니다..

bomul1128 2년 전 2

제 해결 방법 공유해드립니다.

단순하게 입력값을 받는 방법 문제였습니다.

input() 대신 sys.stdin.readline() 으로 입력값을 받으니 통과됐습니다!

seho27060 2년 전 0

엇 그럼 제 코드는 다시 훑어봐야 겠네요 ㅋㅋㅋㅋ

답변 감사드립니다!

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

문제

문제

출처

ICPC

힙 구조 문제 시간 초과가 뜹니다

bomul1128 2년 전 1

seho27060 2년 전 1

bomul1128 2년 전 2

seho27060 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말