글 읽기 - python3 시간초과 // 제코드에서 시간이 오래걸리는곳이 궁금합니다

erurang 3년 전 0

저는 접근을 이렇게했습니다.

1. 소수를 판별하는 함수를 만들자 (prime_num_check(number))

2. 일단 최대케이스가 10000이니까 10000까지 소수리스트를 만들자 (prime_number)

3. 23번줄은 숫자 입력(a)을 받고

4. 26번부터는 일단은 입력값 보다 작거나 같은 소수 index위치를 찾았습니다.

5. 그래서 입력받은숫자와 prime_number[index]를 하나하나 비교했습니다.

답은 정상적으로 나옵니다.

해답은 아직 안봤습니다.

제 코드에선 잦은 for문과 while문이 있는것이 시간초과의 원인인가요?

아니면 10000개의 소수리스트를 만드는것에 문제가 있는걸까요?

import sys

# 1 소수리스트 만들기
# 2 소수판단함수
# 3 합산하는 함수
# 4 합산하는 함수 리스트

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

prime_number = []
prime_number_sum = []

def prime_num_check(number):
    for index in range(2,number):
        if number % index == 0:
            return False
    return True

for i in range(10001):
    if prime_num_check(i):
        prime_number.append(i)

for _ in range(n):
    a = int(sys.stdin.readline())

    for index in range(len(prime_number)):
        if a <= prime_number[index]:
            while True:
                if index == -1:
                    break

                for i in range(index, -1, -1):
                    if a == 2 * prime_number[index]:
                        prime_number_sum.append([prime_number[index] - prime_number[index - i], prime_number[index - i],
                                                 prime_number[index]])
                    elif a == prime_number[index] + prime_number[index - i]:
                        prime_number_sum.append([prime_number[index]-prime_number[index-i],prime_number[index-i],
                                                 prime_number[index]])

                index -= 1

            prime_number_sum.sort()
            print(prime_number_sum[0][1],prime_number_sum[0][2])
            prime_number_sum = []
            break

kyo20111 3년 전 0

python으로 시간초과가 나면 pypy로 제출해보세요

시간초과가 아니라 틀렸습니다가 나옵니다

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

문제

문제

출처

ICPC

python3 시간초과 // 제코드에서 시간이 오래걸리는곳이 궁금합니다

erurang 3년 전 0

kyo20111 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말