글 읽기 - 시간 초과 관련 (Python3와 PyPy3 차이)

bjchae9627 4년 전 0

안녕하세요, 아래 코드를 Python 3로 제출했을 때 계속 시간 초과가 발생하여서 어디서 들은 게 있었던 것 같아서 PyPy3로 제출했는데 통과하였습니다.

동일한 코드인데 시간 제한 기준이 다른 이유를 알 수 있을까요?

처음에는 abs 함수가 크게 시간을 잡아먹나 싶어서 구글링해서 찾아본대로 heap에 추가할 때 [절댓값, 원래값]의 tuple로 넣었는데 역시 시간초과 오류가 발생하더라구요ㅠ

추가로, 혹시 Python3에서도 분명 통과할 수 있는 코드가 있을텐데 어떤 부분으로 인해서 제 코드가 통과하지 않는지도 알려주신다면 정말 감사합니다.

개인적으로는 49~51 번째 줄 때문이 아닐까 싶기도 한데 최소힙/최대힙 모두 거의 동일한 방법의 코드가 Python3로 통과해서 더 이해가 가지 않네요ㅠㅠ

import sys

heap = [None]
len_heap = 0


def min_heapify(i):
    global heap, len_heap
    left = 2 * i
    right = 2 * i + 1
    if right <= len_heap and (abs(heap[right]) < abs(heap[i]) or (abs(heap[right]) == abs(heap[i]) and heap[right] < heap[i])):
        smallest = right
    else:
        smallest = i

    if left <= len_heap and (abs(heap[left]) < abs(heap[smallest]) or (abs(heap[left]) == abs(heap[smallest]) and heap[left] < heap[smallest])):
        smallest = left

    if smallest != i:
        temp = heap[i]
        heap[i] = heap[smallest]
        heap[smallest] = temp
        min_heapify(smallest)


n = int(input())

for _ in range(n):
    x = int(sys.stdin.readline().rstrip())
    # Pop
    if x == 0:
        # Heap이 비어있는 경우
        if len_heap == 0:
            print(0)
        # Heap에 값이 들어있는 경우
        else:
            print(heap[1])
            heap[1] = heap[len_heap]
            del heap[len_heap]
            len_heap -= 1
            min_heapify(1)

    # Insert
    else:
        len_heap += 1
        heap.append(x)
        if len_heap > 1:
            val = len_heap
            while val > 0:
                min_heapify(val)
                val = val // 2

dyk777 4년 전 0

python3와 pypy3의 시간 제한은 동일합니다.

pypy3가 일반적으로 python3에 비해 더 빠르다고 알고 있는데, 아마 그 때문이라고 생각되네요.

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

문제

문제

출처

ICPC

시간 초과 관련 (Python3와 PyPy3 차이)

bjchae9627 4년 전 0

dyk777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말