꾸준히 개발하기

소수판별 알고리즘과 시간초과의 늪의 반복이었던 문제... 계속 풀었던 골드바흐 파티션 문제 중 아마 시간이 제일 짧게 주어졌던 문제였던 듯 하다. 물론 그거 고려 안하고 무작정 들박했다가 처참한 시간 초과의 늪에 빠졌다.

처음에는 최대 MAX 값만큼 안 돌리고 테스트케이스 내에서 max값까지만 에라토스테네스의 체를 이용하는 것도 고려해봤는데 여전히 시간초과가 나더라. 생각해보면 max값까지 돌리나 백만까지 돌리나 시간은 크게 차이가 없었다. 그러면 이제 따져볼건 골드바흐 파티션을 구하는 과정에서 불필요한 for문이 있다는 거였다. 아무리 생각해도 for문을 2개를 돌려야될 것 같다고 생각하면서 break문 열심히 넣어줘도 계속 시간초과가 났다.

for문을 1개로 줄여야 통과될 것 같은데, 하면서 보다가 답을 찾아냈다.

-> 굳이 for문을 2개 돌릴 필요 없이, 앞에서부터 보는거 + 뒤에서부터 보는거 는 for문 1개로 충분했다!

흐뭇하게 .. 시간초과의 늪에서 벗어났다. 코드는 다음과 같다.

def getPrimes(MAXCASE):
    erato = [True] * (MAXCASE + 1)
    erato[0], erato[1] = False, False

    for i in range(2, int(MAXCASE ** 0.5) + 1):
        if erato[i] == True:
            for j in range(i + i, MAXCASE + 1, i):
                erato[j] = False
    return erato


erato = getPrimes(1000001)
t = int(input())

for _ in range(t):
    num = int(input())
    cnt = 0
    for i in range(2, num // 2 + 1):
        if erato[i] and erato[num - i]:
            cnt += 1
    print(cnt)

굳이 에라토스테네스의 체를 함수로 선언해준 이유는... 입력받은 숫자 중 max값까지만 소수판별을 하려고 했었다 원래는 ^.T 중첩 for문을 줄여야 시간복잡도를 확 줄일 수 있다고 또다시 몸으로 깨달은 문제였다.