글 읽기 - 시간초과 문제 해결방법

dohjh0219 1년 전 0

해당 문제의 예시 및 여러가지 반례들에 정상적으로 코드가 작동하나 시간초과로 실패합니다. 시간초과를 줄이기 위한 효과적인 해결방안이 있으시다면 알려주십시오.!!

# 9020 골드바흐의 추측(시간초과 오답 코드. 답은 맞으나 시간초과 해결 필요.)

import sys
import math

n=int(sys.stdin.readline())

def num(num): # 소수 구하는 함수
    if num == 1:  # 1은 소수가 아니므로 False 반환
        return False
    else :
        for i in range(2,int(math.sqrt(num))+1) : # sqrt는 제곱근 기능임. 
            if num%i == 0: # num이 i에 의해서 나누어 떨어지면 소수가 아니라는 의미이므로 False 반환. 
                return False
        return True

all_list = list(range(2,10000)) # 문제에서 주어진 범위 리스트 생성.
save_list=[]


for i in all_list : # all_list에 있는 범위 만큼 소수 검색.
    if num(i):
        save_list.append(i) # 소수라면 save_list에 append. 즉 save_list에는 범위 내 소수가 모두 저장됨.and
        
result=[]
cha=[]

for i in range(n):
    num=int(sys.stdin.readline())
    result.clear()
    cha.clear()
    
    for j in save_list:
        if num-j>=0:
            if save_list.count(num-j)>0:  # num에 대응하는 값이 소수 리스트에 있는가?
                result.append([j,num-j])
            else:
                continue
    
    if len(result)>0:
        for k in range(len(result)):
            cha.append((result[k][0]-result[k][1])**2)
        print(result[cha.index(min(cha))][0],result[cha.index(min(cha))][1],sep=' ')
    else:
        print(0,num,sep=' ')

cinador 1년 전 1

num - j 가 소수인지 확인하는데에 save_list에 count함수를 적용한 것이 가장 큰 원인이라고 생각됩니다. count 함수는 리스트의 원소를 전부 확인합니다.

10000 이하의 소수는 약 1200개인데 만약 1000번째 소수 하나만 입력으로 넣어줘도 if num - j >= 0에 1000번 걸리기 때문에 이 부분에만 약 120만번의 연산이 진행됩니다.

count 함수를 안쓰고 num - j가 소수인지 확인하는 방법을 생각해보시면 좋을 거 같습니다. (사실 num - j에 위에서 정의한 소수 판별 함수를 쓰는게 위 방법보다 더 효율적입니다.)

dohjh0219 1년 전 0

정성스러운 답변 감사합니다! 잘 적용해 보도록 하겠습니다~~!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 문제 해결방법

dohjh0219 1년 전 0

cinador 1년 전 1

dohjh0219 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말