글 읽기 - 시간초과 질문이요!

shockboy90 7년 전 0

에라토스테네스의 체 참고해서 한건데도 시간초과가 나오네요...
어떤게 잘못되었나요!?

a,b=map(int,raw_input().split())

result = []
candidates = range(a,b+1)
base = 2
product = base
count=0
while candidates:
    while product < b+1:
        if product in candidates:
            candidates.remove(product)
        product = product+base
    result.append(base)
    count+=1
    base = candidates[0]
    product = base
    del candidates[0]
result.append(base)
del result[0]    
for i in range(count):
    print result[i]

etaehyun4 7년 전 0

Python List에서 Remove Operation은 시간복잡도가 최악에 O(N) 입니다.

그렇게 되면 구현하신 알고리즘은 O(N^2) 가 되어 시간 초과가 발생합니다.

remove를 쓰시지 마시고 그 값이 체크되었는지 True, False 등으로 저장해놓으시면 효율적으로 바꿀 수 있습니다

shockboy90 7년 전 0

좋은 답변 감사드립니다.

체크되었는지 True, False부분에 대해 예시 코드좀 혹시 알려주실 수 있나요?
전혀 감이 안잡히네요ㅠㅠ

etaehyun4 7년 전 0

구글링에서 찾은 Pseudocode입니다

http://www.algolist.net/Algorithms/Number_theoreti...

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

문제

문제

출처

ICPC

시간초과 질문이요!

shockboy90 7년 전 0

etaehyun4 7년 전 0

shockboy90 7년 전 0

etaehyun4 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말