글 읽기 - 시간 초과를 최대한 줄여봤는데 잘 모르겠습니다..!

rjsdud2085 1년 전 0

일단은 "에라토스테네스의 체"를 이용해서 입력 받은 input마다 primeList를 만들었습니다.

그리고 골드바흐 파티션으로 표현되는 두 수가 소수인지 primeList 속에서 비교해보는 방식으로 구현을 했는데 계속 시간 초과가 뜨네여..

최대한 검사 수를 줄이려고 해봤는데 어디가 문제인지 잘 모르겠습니다.

이렇게까지 실패가 뜬 건 처음이어서 질문 게시판에 글을 올려봅니다..!

답변해주시면 정말 감사하겠습니다!!ㅠㅠ

import math

T = int(input())
num = [0] * T

# 테스트케이스 만큼 input 입력 받기
for i in range(T) :
    num[i] = int(input())

# 범위 내 소수 리스트를 return하는 함수(에라토스테네스의 체)
def prime_list(num) :
    m = int(num ** 0.5)
    che = [True] * num

    for i in range(2, m + 1) :
        if che[i] == True :
            for j in range(i + i, num, i) :
                che[j] = False

    return [i for i in range(2, num) if che[i] == True]

# 테스트케이스 만큼 반복
for i in range(T) :
    result = []
    result.clear()
    primeList = prime_list(num[i])

    # 입력 받은 num의 절반까지만 검사
    for j in primeList:
        # 절반만 검사
        if j > int(num[i]/2) :
            continue
        # 입력 받은 num에서 j를 뺀 수를 소수인지 검사
        if primeList.count(num[i] - j) == 0 :
            continue
        else :
            result.append(j)

    # (소수 + 소수)가 한 쌍밖에 나오지 않았다면 바로 출력
    if len(result) == 1 :
        print(f"{result[0]} {num[i] - result[0]}")
    # 한 쌍 이상이라면 마지막 값을 출력
    else :
        lastValue = result.pop()
        print(f"{lastValue} {num[i] - lastValue}")

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

문제

문제

출처

ICPC

시간 초과를 최대한 줄여봤는데 잘 모르겠습니다..!

rjsdud2085 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말