17103번 - 골드바흐 파티션
1. 26번째 줄에서 in 연산자의 시간복잡도는 O(n) 입니다.
이걸 O(1), 아니면 적어도 O(log n) 까지 줄이는 검색 알고리즘 또는 자료구조를 찾으셔야 합니다.
.
2. prime_set 은 매 입력 한 줄 마다 새로 만들 필요가 없어보입니다.
n = 1000000 일 때 한 번만 prime_set 을 만들고, goldbach_partition 에서는 이미 만들어진 prime_set 에서 원하는 부분만 따로 추려서 계산하는 것도 좋을 듯 합니다.
스포일러: 이런 방식을 "런타임 전의 전처리" 라고 부르기도 합니다. 일부 사람이 이 문제에 이 태그를 붙이는 것을 추천했지만, 다수의 의견은 아닌듯 합니다.
다들 감사합니다!!
prime_set을 한번만 만들도록 하고, in 연산자 안쓰도록 하니까 풀리네요.!!
댓글을 작성하려면 로그인해야 합니다.
garamieeeeee 1년 전
에라토스테네스의 체 써서 소수 리스트 구한 다음에
for e in prime_set:
if e > n-e: break
if (n-e) in prime_set:
cnt += 1
이런식으로 e <= n-e인 동안에 두 수가 둘다 prime_set에 있는지 확인하면서 카운트 늘리는 방법인데
여기서 반복문을 더 줄일 수 있을까요? 시간초과가 나서요 ㅠㅠ