글 읽기 - 파이썬 시간초과

taewan2002 1년 전 0

다른 언어로는 통과가 되는 알고리즘인데 python3에선 시간초과, pypy3에서는 메모리 초과가 발생합니다.

혹시 이 알고리즘이 정답이 아닌 것 일까요?

import sys
import bisect
input = sys.stdin.readline

def get_max(node):
    global total_list
    global cnt
    lb = bisect.bisect_left(total_list, node)
    if lb > 0:
        left = high[total_list[lb - 1]]
    else:
        left = 0
    if lb < len(total_list):
        right = high[total_list[lb]]
    else:
        right = 0
    high[node] = max(left, right) + 1
    cnt +=  max(left, right) + 1
    total_list.insert(lb, node)

    return high[node]

n = int(input())
total = 0
total_list = []
cnt = 0
high = [0] * (n + 1)
tmp = int(input())
total_list.append(tmp)
print(cnt)
for i in range(1, n):
    total += get_max(int(input()))
    print(cnt)

hjroh0315 1년 전 0

"오타/오역/요청"은 문제 자체의 오류 수정을 요청할 때 글을 쓰는 게시판입니다. "질문"에 올려주세요.

cdw2241 1년 전 0

insert를 하면 뒤에 원소를 다 밀어내니 어마어마한 시간이 걸리지 않을까요?

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

문제

문제

출처

ICPC

파이썬 시간초과

taewan2002 1년 전 0

hjroh0315 1년 전 0

cdw2241 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말