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

sjyoo1572 2년 전 0

에라토스테네스의 체를 통해 시간을 단축 시켜야 한다는 것은 이해 했습니다

그래서 저는 소수 리스트를 만들어서 접근을 해보고자 했습니다

for문으로 소수 리스트 전부를 읽는과정에서 시간 초과가 나는건가요?

시간을 단축시킬 방법이 어떤게 있을까요 ㅠㅠ

#-----------------에라토스테네스의 체----------
m = 1
n = 10001

suso_list = []

a = [True for i in range(n)]

for i in range(2, int(n**0.5)+1):
    if a[i] == True:
        for j in range(2*i, n, i):
            a[j] = False

for i in range(m,n):
    if i>1 and a[i] == True:
        suso_list.append(i)             #소수 리스트만들기

        

T = int(input())    #반복횟수

for k in range(T):
    k = int(input())
    dic = {}

    for i in suso_list:
        if k-i in suso_list:            #k에서 i를 뺀값이 소수리스트에 있으면
            if i <= k-i:                #첫번째 값이 입력받은 값보다 작거나 같을 때
                dic[(k-i)-i] = [i, k-i] #딕셔너리에 두값의 차를 키로하여 두 값 리스토로 저장
                 
            else:
                dic[i-(k-i)] = [k-i, i] 
            
    key_list = list(dic.keys())         #두값의 차이들만 모아서 차이 리스트 생성
    print(dic[min(key_list)][0],dic[min(key_list)][1]) #두 소수의 차이가 가장 작은 것만 가져와서 하나씩 출력
            

ai4youej 2년 전 1

질문자님께서 올려주신 코드를 최대한 수정하지 않고 바꿔서 제출해보니, 맞았습니다!! 가 나왔습니다.

이 코드가 시간 초과가 나는 이유는 어떤 원소 i가 list 안에 존재하는지 확인하는데 걸리는 시간이 O(len(list)) 이기 때문입니다.

즉, 어떤 원소 i가 존재하는지 확인하는 시간이 O(1)이 걸리는 set 자료구조를 사용하면, 코드를 최대한 바꾸지 않고 문제를 해결할 수 있습니다.

(물론 set을 사용한다면 append 대신 add를 써야합니다.)

아래는 수정된 코드입니다.

추가로, 맞았습니다!!를 받으신 후에 다른 사람들의 코드를 보시는 것도 좋을 거 같습니다.

#-----------------에라토스테네스의 체----------
m = 1
n = 10001

suso_list = set() # Set으로 바꿔줍니다

a = [True for i in range(n)]

for i in range(2, int(n**0.5)+1):
    if a[i] == True:
        for j in range(2*i, n, i):
            a[j] = False

for i in range(m,n):
    if i>1 and a[i] == True:
        suso_list.add(i)             # suso_list의 자료구조가 set이므로 add 메소드를 사용합니다

        

T = int(input())    #반복횟수

for k in range(T):
    k = int(input())
    dic = {}

    for i in suso_list: 
        if k-i in suso_list:            # 그러면 이 줄을 실행하는데 걸리는 시간이 대폭 짧아집니다
            if i <= k-i:                
                dic[(k-i)-i] = [i, k-i] 
                 
            else:
                dic[i-(k-i)] = [k-i, i] 
            
    key_list = list(dic.keys())    
    print(dic[min(key_list)][0],dic[min(key_list)][1])
                               

sjyoo1572 2년 전 0

이제 확인했네요 ㅜㅜ 정말 감사합니다!!

set 자료구조는 생소해서 잘 안 써봤는거 같은데 이런식으로 시간을 절약 할 수 있군요!

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

문제

문제

출처

ICPC

파이썬 9020번 시간초과 질문

sjyoo1572 2년 전 0

ai4youej 2년 전 1

sjyoo1572 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말