글 읽기 - 파이썬 9020 시간 초과

kjmin2000 2년 전 0

나름 생각해보고 짰는데 뭔가 시간이 초과될 것 같다는 느낌적인 느낌이 들었는데 역시...

시간 초과가 뜹니다. 어디서 시간이 오래 걸리는지 조언 부탁드리겠습니다!

그리고 혹시, 함수를 선언(def)하고 그 함수에서 다른 함수를 호출해도 시간복잡도가 올라가나요?

# 소수인지 아닌지 판별하는 함수
def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                return False
        return True

# 정해진 숫자까지 소수를 구하는 함수
def primeSection(num):
    all_list = list(range(2, num))
    set_list = []
    for i in all_list:
        if isPrime(i):
            set_list.append(i)

    return set_list

# 실제 입력된 범위에서 소수를 구하는 코드
case = int(input())
for i in range(case):
    N = int(input())
    cal_list = primeSection(N)  # 계산하기 위한 리스트 선언
    idx = int(len(cal_list) / 2)  # 입력된 숫자까지의 소수들 중, 그 중앙에 위치한 숫자의 인덱스

    while True:
        if N - cal_list[idx] in cal_list:
            print(cal_list[idx], N - cal_list[idx], sep=" ")
            break
        else:
            idx -= 1

qvixnh22 2년 전 1

예제 입력과 같은 상황을 생각해 봅시다.

첫 번째 수 8에 대해서 cal_list는 [2,3,5,7]이 될겁니다.

두 번째 수 10에 대해서 cal_list는 [2,3,5,7]이 되고, 세번째 cal_list는 [2,3,5,7,11,13]이 될겁니다.

반대로, 순서가 16, 10, 8 순서대로 들어오는 상황을 생각해 보면,

첫번째로는 [2,3,5,7,11,13]의 list를 받아 왔지만, 두번째는 [2,3,5,7]을 다시 계산해야 합니다.

즉, primeSection 함수는 N번 반복해서 실행하게 됩니다.

중복되는 계산을 줄일 방법에 대해 잘 생각해보세요.

kjmin2000 2년 전 1

말씀을 읽어보고 곰곰이 생각해보니

primeSection 함수가 굳이 필요가 없다는 생각이 들었습니다!

함수를 없애고 다시 구현해봤더니 답을 맞췄습니다!

조언 감사합니다 :D 복 받으세요!

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

문제

문제

출처

ICPC

파이썬 9020 시간 초과

kjmin2000 2년 전 0

qvixnh22 2년 전 1

kjmin2000 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말