글 읽기 - 파이썬 시간초과

pheonixkid 4년 전 0

아래 코드처럼 에라토스테네스의 체를 이용해서 풀려고 하는데 제가 제대로 구현했는지 잘 모르겠어서 확인 하려고 올렸습니다.

만약 맞게 구현했다면 시간 초과가 나오는데 어느 부분에서 시간 초과가 뜨는지 잘 이해가 안됩니다.

첫번째 또는 두번째 룹을 잘못 구현한것같기도 한데 정확하게 어디서 문제인지를 설명해주실 분 있으신가요?

import sys, math, time
x, y = sys.stdin.readline().split()
x = int(x)
y = int(y)
prime = []

start = time.time() # 시간 확인용
for i in range(2, y+1):
    prime.append(i)

for i in range(2, int(math.sqrt(y+1))):
    if i in prime:
        for j in range(i*2, y+2, i):
            if j in prime:
                prime.remove(j)

finish = time.time() # 시간 확인용
for i in range(len(prime)):
    if prime[i] >= x:
        print(prime[i])
print(finish - start) # 시간 확인용

ho94949 4년 전 0

remove 함수는 최악의 경우 리스트의 길이에 비례한 시간이 걸립니다.

pheonixkid 4년 전 0

감사합니다.. 덕분에 문제 해결이 되었습니다!!

remove함수의 걸리는 시간을 찾다가 리스트 자체가 커지면 커질수록 시간도 길어진다는것을 알게 되어 set로 바꿔서 구현하니까 시간 문제는 해결되었습니다! ㅎㅎ

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

문제

문제

출처

ICPC

파이썬 시간초과

pheonixkid 4년 전 0

ho94949 4년 전 0

pheonixkid 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말