글 읽기 - 정답주의)두 코드의 알고리즘이 같다고 생각하는데 왜 결과가 다른지 모르겠습니다

kangwh0617 2년 전 0

위 코드는 정답이고 아래 코드는 시간초과네요

두 코드 모두 에라토스테네스의 체를 한번 돌리고 1부터 n까지 순회하며 가장 작은 소인수 배열을 생성하는데 왜 딕셔너리를 이용하였을때 시간초과가 날까요?

제 생각에는 오히려 배열을 선언해서 할 때가 0부터 5000000까지 돌면서 배열을 생성하니 시간이 더 오래 걸릴거라고 생각했는데 아니더라구요

#정답코드,배열사용
def p(n,d): #에라토스테네스의 체
    s = [1] * n
    m = int(n**0.5)
    for i in range(2,m+1):
        if s[i] == 1:#소수인 경우
            for j in range(i+i,n,i):#소수의 배수에 대해
                s[j] = 0
                if d[j] == j:
                    d[j] = i #가장 작은 소인수 입럭
a = int(input())
b = list(map(int,input().split()))
g = [i for i in range(5000001)]
c = p(5000001,g)
for i in range(a):
    e = []
    f = b[i]
    while f > 1:
        e.append(g[f])
        f = f // g[f]
    for i in e:
        print(i,end = " ")
    print()

#시간초과,딕셔너리 사용
def p(n,dict):
    s = [1] * n
    m = int(n**0.5)
    for i in range(2,m+1):
        if s[i] == 1:
            dict[i] = i
            for j in range(i+i,n,i):
                s[j] = 0
                if j not in dict:
                    dict[j] = i
    for i in range(m,n):
        if s[i] == 1:
            dict[i] = i #탐색안된부분의 소수의 소인수를 입력
    
a = int(input())
b = list(map(int,input().split()))
g = dict()
c = p(5000001,g)
d = 0
for i in range(a):
    e = []
    f = b[i]
    while f > 1:
        e.append(g[f])
        f = f//g[f]
    for i in e:
        print(i,end = " ")
    print()

shjohw12 2년 전 0

딕셔너리가 해싱으로 구현되어있는 것으로 아는데, 시간복잡도는 O(1) 이지만 list보다는 당연히 느립니다

kangwh0617 2년 전 0

같은 O(1)짜리 탐색이라도 조금 더 느리군요.... 배워갑니다 감사합니다

djm03178 2년 전 0

코드는 삭제하지 말아주세요. 나중에 질문을 보는 사람에게 도움이 될 수도 있는 자료입니다.

kangwh0617 2년 전 0

수정했습니다

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

문제

문제

출처

ICPC

정답주의)두 코드의 알고리즘이 같다고 생각하는데 왜 결과가 다른지 모르겠습니다

kangwh0617 2년 전 0

shjohw12 2년 전 0

kangwh0617 2년 전 0

djm03178 2년 전 0

kangwh0617 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말