[백준 / Python] 9020번 : 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

---

 

---

 

첫번째 시도

import sys
input = sys.stdin.readline
 
numList = [0] * 2 + [1] * 9999
 
for i in range(2,101):
    try:
        cnt = 2
        while True:
            numList[i * cnt] = 0
            cnt += 1
    except:
        continue
 
for j in range(len(numList)):
    if numList[j]:
        numList[j] = j
 
for _ in range(int(input())):
    num = int(input())
    result = []
    for a in numList[1:int(num/2)+1]:
        if a:
            for b in numList[int(num/2):num]:
                if a+b == num:
                    result.append([a,b])
                    break
    print(result[-1][0],result[-1][1])

 

예전에 소수찾기에서 사용했던 코드를 그대로 가져와 수정하면서 사용하니 불필요한 연산이 늘어난 거 같고 마지막 반복문에서 정답인 모든 경우의 수를 append 하다보니 이 또한 시간복잡도가 굉장히 늘어난 이유인 것 같다.

 

두번째 시도

import sys
input = sys.stdin.readline
 
numList = [0] * 2 + list(range(2,10001))
 
for i in range(2,101):
    cnt = 2
    try:
        while True:
            numList[i * cnt] = 0
            cnt += 1
    except:
        continue
 
for k in range(int(input())):
    n = int(input())
    a = int(n/2)
    b = int(n/2)
    while True:
        if a in numList and b in numList:
            print(a,b)
            break
        a -= 1
        b += 1

 

첫번째 코드에서 수정을 통해 정답을 유추할 길이 없어보여 새로 짜보기로 했다.

우선 첫번째로 소수로 이루어진 리스트가 필요하다. 소수를 판별하는 것이 아니기 때문에 0 또는 1로 이분 할 필요가 없다. 대신 소수가 아닌 것은 0으로 두어 시간복잡도를 최소로 하여 할 수 있는 최소한의 구분은 해둔다.

그 후 입력값은 무조건 짝수라는 조건이 있기 때문에 별 다른 조치없이 반으로 나누고 두 변수에 저장한다. 그리고 무한루프를 생성해 하나는 1씩 줄이고 하나는 1씩 늘려가며 그 수가 소수 리스트에 존재할 경우 답을 출력한다.

첫번째 코드보단 연산이 확실히 줄었지만 여전히 시간 초과가 뜬다. 

 

세번째 시도

import sys
input = sys.stdin.readline
 
numList = [0] * 2 + list(range(2,10001))
 
for i in range(2,101):
    cnt = 2
    try:
        while True:
            numList[i * cnt] = 0
            cnt += 1
    except:
        continue
 
for k in range(int(input())):
    n = int(input())
    a = int(n/2)
    b = int(n/2)
    while True:
        if a in numList[:int(n/2)+1] and b in numList[int(n/2):]:
            print(a,b)
            break
        a -= 1
        b += 1

 

어디서 불필요한 연산이 많이 되고 있을까 를 찾던 중 리스트에서 in 함수가 시간복잡도가 O(N)으로 꽤 크다는 글을 어디선가 봤던 기억이 났다. 그래서 마지막에 순회해야할 리스트의 범위를 손봤더니 통과했다 !