글 읽기 - 골드바흐 시간초과 이유 python3

tom3k 3년 전 0

안녕하세요. 골드바흐 문제에서 값은 출력되는 것을 확인했는데 시간초과가 납니다.

count 함수 때문일까요? 혹시 코드를 디벨롭 해주신다면 어떤 부분을 바꾸실 것 같나요?

#소수 판별
def isPrime(n):
    return all([(n%i) for i in range(2,int(n**0.5)+1)]) and n>1

#2~9999까지 포함되어 있는 소수 리스트 생성
primeNum = []
for i in range(2,10000):
    if isPrime(i):
        primeNum.append(i)

        
testCase = int(input())
for _ in range(testCase):
    n = int(input())
    temp = [] #입력값 n의 골드바흐 파티션을 담을 리스트
    for prime in primeNum:
        if prime>n/2:
            break
        if primeNum.count(n-prime) == 1: #count 연산을 넣어서 그런걸까요
            temp.append(prime)
            temp.append(n-prime)
    index=len(temp)/2
    temp = sorted(temp) 
    print(f'{temp[int(index)-1]} {temp[int(index)]}')
    
 

dlrudwo4685 3년 전 0

temp의 갯수가 많으면 많을수록 정렬하는데 시간이 많이 걸려서 시간 초과가 일어나는 것 같아요

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

문제

문제

출처

ICPC

골드바흐 시간초과 이유 python3

tom3k 3년 전 0

dlrudwo4685 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말