백준9020 - 골드바흐의 추측 Python

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

문제는 정수 n 이 주어질 때, 가장 차이가 적으며 합이 n을 만족하는 두 소수를 찾아 출력하는 문제다.

 

이전 포스팅했던 에라스토테네스의 체를 활용하여 소수를 판정하는 테이블을 만든 뒤, 

반복문을 통해 조건을 만족하는 값을 찾았다.

 

처음 작성한 코드

# table = 에리스토테네스의 체로 소수판정한 리스트 | n = 정수
  
def act (table, n) :
  x,y = 10000,0
  for i in range(n-1, 0, -1) :
    if table[i] :
      for j in range(n-1, 0, -1) :
        if table[j] and i + j == n and abs(x - y) > abs(i - j):
          x,y = i,j
  
  return '{} {}'.format(x,y) if y > x else '{} {}'.format(y,x)

처음에는 다음과 같이 작성해서 제출했는데, 시간 초과로 풀이가 불가했다.

이 경우는 n보다 작은 값부터 차례대로 조건을 만족하는 값을 찾는데, 

가능한 경우를 모두 순회하기 때문에 시간복잡도에서 불리할 수밖에 없었다.

 

이에 대해 고민을 하다 예제의 입력값 중 하나인 n에 10이 들어오는 경우를 보고 힌트를 얻었다.

두 소수의 합이 10이 되는 경우는 (3,7), (5,5), (7,3)이기 때문에

두 소수의 차가 가장 작은 경우를 찾으려면 n의 가운데부터 찾는 경우가 더 유리하리라 생각했다.

 

수정한 코드

def act (table, n) :
  for i in range(n//2, n) :
    if table[i] :
      for j in range(n//2, 0, -1) :
        if table[j] and i + j == n :
          return '{} {}'.format(i,j) if j > i else '{} {}'.format(j,i)

 

따라서 위와 같이 코드를 수정하여, n의 가운데부터 찾되 조건이 맞다면 바로 반환할 수 있도록 코드를 수정해서 시간초과를 해결했다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  _, *arr = list(map(int, data))
  table = primeTable()
  result = list(map(lambda x : act(table, x), arr))
  print('\n'.join(result))
  
def primeTable () :
  limit = 10001
  table = [True] * limit
  table[0] = table[1] = False
  
  i = 2
  while (i**2 <= limit) :
    if table[i] :
      for j in range(i**2, limit, i) :
        table[j] = False
    i += 1
  return table
  
def act (table, n) :
  for i in range(n//2, n) :
    if table[i] :
      for j in range(n//2, 0, -1) :
        if table[j] and i + j == n :
          return '{} {}'.format(i,j) if j > i else '{} {}'.format(j,i) 

solution(input_data)