1. 일단 prime 함수의 6번째 줄이 비효율적입니다. num을 int(num**0.5) + 1로 바꾸는 것을 추천드립니다.
2. 그래도 시간초과가 날 거 같습니다. 이러한 이유는 여러 군데에서 발견됩니다. 그 중 첫 번째로는 remove 메소드를 들 수 있습니다. remove 매소드는 O(1)이 아닌 통상 O(N)에 작동합니다. 여기서 N은 리스트의 길이입니다.
3. 그렇다면 이를 해결하기 위해서, 소수가 아니라면 리스트에서 '지워주는' 느낌으로는 시간제한을 피하기 힘듭니다. 따라서 boolean list를 만들고 (모든 원소가 True or False인 리스트), 이때 소수가 아니라면 False로 바꿔주면 됩니다. 리스트에서 인덱스에 해당하는 원소를 지우는 시간복잡도는 O(1)이기 때문이죠!
4. 이 모든 과정을 다 적용해도, 시간 초과가 날 수 있습니다. 이는 사실 prime 함수가 필요가 없기 때문입니다. 그 이유는, 에라토스테네스의 체에서, 코드만 잘 짰다면, 아직 삭제되지 않은 원소는 소수이기 때문입니다.
kdg1385 2년 전
안녕하세요. 시간초과에 허덕이는 코린이입니다.
1929번 문제를 푸는 도중 시간 초과만 나와서 어떤 방식으로 해야 해결 될지 궁금합니다.
에라토스테네스의 체를 나름 이용 했지만 역시 시간 초과가 나왔습니다.
조언 해주시면 감사하겠습니다.