21/01/10 TL. 백준 9020

9020 골드바흐의 추측

 

내 전 코드

import sys
import bisect


def run():
    era = eratos(10000)
    for _ in range(int(sys.stdin.readline())):
        num = int(sys.stdin.readline())
        # 현재 입력된 짝수보다 작은 최대의 소수.
        bp = bisect.bisect_left(era, num)
        result = list()

        for i in range(bp):
            for j in range(bp, i - 1, -1):
                if era[i] + era[j] == num:
                    result = [era[i], era[j]]
                    break
        a, b = result
        print(a, b)



def eratos(num):
    arr = [True] * (num + 1)
    arr[0], arr[1] = False, False

    m = int((num + 1) ** 0.5)
    for i in range(2, m):
        if arr[i] == True:
            for j in range(i + i, num, i):
                arr[j] = False

    return [i for i in range(num + 1) if arr[i] == True]


if __name__ == '__main__':
    run()

수정한 코드 

import sys
import bisect

def run():
    era = eratos(10000)
    for _ in range(int(sys.stdin.readline())):
        num = int(sys.stdin.readline())

        # 어차피 입력되는 건 짝수인데, 짝수는 2개의 홀수로 나뉘어질 수 있다. 그 홀수는 최대의 소수가 될 수 있을 것.
        # bp는 반으로 나눴을 때 그것보다 작은 가장 큰 소수(최대 딱 절반)의 index. b2는 num보다 작은 가장 큰 소수
        bp = bisect.bisect_right(era, num // 2) - 1
        bp2 = bisect.bisect_right(era, num) - 1
        check = False
        for i in range(bp, -1, -1):
            for j in range(bp, bp2, 1):
                if era[i] + era[j] == num:
                    print(era[i], era[j], sep=" ")
                    check = True
                    break
            if check:
                break


def eratos(num):
    arr = [True] * (num + 1)
    arr[0], arr[1] = False, False

    m = int((num + 1) ** 0.5)
    for i in range(2, m):
        if arr[i] == True:
            for j in range(i + i, num, i):
                arr[j] = False

    return [i for i in range(num + 1) if arr[i] == True]


if __name__ == '__main__':
    run()

위 코드에서 문제점은 최적화가 잘못됐다는 점이다. 짝수는 홀수 + 홀수 꼴로 나누어진다는 점을 착안해서, 반으로 나누고 해당 부분에서 좌우로 이동하면서 값을 찾는다면, 성능을 개선시킬 수 있을 거라는 생각을 못했다. 그 부분을 수정한 것이 밑의 코드이다.

 

다른 사람의 풀이

from sys import stdin
input = stdin.readline

T = int(input())
answer = ""
result = [False, False, True] + [True, False] * 5000
for number in range(3, 101, 2):
    if result[number]:
        result[number*2::number] = [False] * len(result[number*2::number])

for tc in range(T):
    N = int(input())
    if N == 4:
        answer += "2 2\n"
        continue
    harf_N = N//2
    if not harf_N % 2:
        harf_N += 1
    for i in range(harf_N, N, 2):
        if result[i] and result[N-i]:
            answer += "{} {}".format(N - i, i) + "\n"
            break
print(answer, end="")

 

 이 사람은 아예 2는 True로 초기화 해놓고 시작했다. 이렇게 해서 시간을 단축시키는 방법이 있을 거라는 생각은 못해봤다. 또, 에라토스테네스의 체를 만드는 방법도 for문을 1번만 사용해서 해결했다. 다음에 에라토스테네스의 체 문제가 나오면 적용해 봐야겠다.

 이 사람도 나와 비슷한 식으로 풀었는데, 이 사람의 경우에는 소수 리스트를 따로 받아온 것이 아니라, 전체 리스트를 가지고 만졌다는 점이다. 생각해보니, 새로 리스트를 만들어 오면 다루기는 편할 수도 있겠으나, 쓸모 없는 메모리를 낭비한 것이라고 생각할 수도 있을 것 같다. 홀수처리를 한 부분이 보이는데, 여기서는 입력이 짝수만 돼있는 것이 전제라서 굳이 할 필요는 없었다는 생각이 든다. 이 사람은 나처럼 for문을 2번 쓴 게 아니라, 애초에 반쪽부터 마지막까지 검사하고, 홀수만 검사한다. 홀수만 검사한다는 점을 잘 파악해서 최대한 연산 수를 줄인 것 같다.