글 읽기 - [python] 9020번 시간초과 질문 있습니다..

lms990427 2년 전 1

소수 리스트 만드는 시간도 최대한으로 줄어봤는데 어디서 시간 초과가 나는지 잘 모르겠습니다.. 도와주세요 ㅠㅠ

nn = int(input())
nlist = []
for q in range(nn):
    n = int(input())
    nlist.append(n)
nmax = max(nlist)
lis = [False, False] + [True]*(nmax-1)
prilis = []
for i in range(2 , nmax + 1):
    if lis[i]:
        prilis.append(i)
    for j in range(2*i,nmax+1,i):
        lis[j] = False
for j in nlist:
    llis = [0, 0]
    for i in prilis:
        if i <= j/2 and j-i in prilis:
            llis[0] = i
            llis[1] = j-i
    print("{} {}".format(llis[0], llis[1]))

djm03178 2년 전 0

in list는 리스트의 처음부터 끝까지 돌면서 그 값이 있는지를 확인하기 때문에 리스트의 길이에 비례하는 시간이 걸립니다. 리스트의 모든 원소에 대해 이러한 탐색을 수행하고 있으니 매 케이스마다 리스트의 길이의 제곱에 비례하는 시간이 걸립니다. lis를 활용해 보세요.

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

문제

문제

출처

ICPC

[python] 9020번 시간초과 질문 있습니다..

lms990427 2년 전 1

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말