파이썬 알고리즘 175번 | [백준 17103번] 골드바흐

175. 골드바흐

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

1차 풀이 (시간 400m/s)

import sys

t=int(sys.stdin.readline().rstrip()) # test case 
lis=[] # 숫자들 다 담을 리스트

for i in range(t) : 
    lis.append(int(sys.stdin.readline().rstrip()))

maxi = max(lis) #가장 큰놈 (소수 여기까지 구할라고)

#소수 구하기 - 에라토스테네 
era=[0]*(maxi+1)
era[1]=1

for i in range(1,maxi) :
    if era[i]==0 :
        #for j in range(i*i, i, maxi) :
        for j in range(i*i, maxi, i) : #간격이 맨 뒤에 
            era[j]=1

# 범위 내에서 소수 쌍 체크
for i in range(len(lis)) :
    sav=[]
    for j in range(2,lis[i]) :
        if era[j]==0 and era[lis[i]-j]==0 : 
            if j<lis[i]-j :
                sav.append((j,lis[i]-j))
            else :
                sav.append((lis[i]-j, j))
    sav=set(sav)
    #print(sav)
    print(len(sav))

# print(era)

• 사전에 순서쌍 다 담음 => 이후에 중복으로 제거!
  

2차 풀이 (시간 240m/s)

import sys

t=int(sys.stdin.readline().rstrip()) # test case 
lis=[] # 숫자들 다 담을 리스트

for i in range(t) : 
    lis.append(int(sys.stdin.readline().rstrip()))

maxi = max(lis) #가장 큰놈 (소수 여기까지 구할라고)

#소수 구하기 - 에라토스테네 
era=[0]*(maxi+1)
era[1]=1

for i in range(1,maxi) :
    if era[i]==0 :
        #for j in range(i*i, i, maxi) :
        for j in range(i*i, maxi, i) : #간격이 맨 뒤에 
            era[j]=1

# 범위 내에서 소수 쌍 체크
for i in range(len(lis)) :
    sav=[]
    for j in range(2,lis[i]//2+1) : #이거 걍 절반까지 돌리면 애초에 중복이 안일어나네
        if era[j]==0 and era[lis[i]-j]==0 : 
   sav.append((j,lis[i]-j))
           

    print(len(sav))

• 해당하는 i번째 lis의 수의 절반까지만 돌리면 애초에 중복이 일어나지 않지
  

<내 틀렸던 풀이, 문제점>

import sys

t=int(sys.stdin.readline().rstrip()) # test case 
lis=[] # 숫자들 다 담을 리스트

for i in range(t) : 
    lis.append(int(sys.stdin.readline().rstrip()))

maxi = max(lis) #가장 큰놈 (소수 여기까지 구할라고)

#소수 구하기 - 에라토스테네 
era=[0]*(maxi+1)
era[1]=1

for i in range(1,maxi) :
    if era[i]==0 :
        #for j in range(i*i, i, maxi) :
        for j in range(i*i, maxi, i) : #간격이 맨 뒤에 
            era[j]=1

# 범위 내에서 소수 쌍 체크
for i in range(len(lis)) :
    sav=[]
    for j in range(2,lis[i]) :
        if era[j]==0 and era[lis[i]-j]==0 : 
            sav.append((lis[i]-j, j))
    sav=set(sav)
    #print(sav)
    print(len(sav))

# print(era)

<반성 점>

• for(시작 , 끝 , 간격) 인데 간격을 가운데로 착각한 데서 시간을 많이 잡아먹었던 점이 아쉽

<배운 점>

• append 할 때 걍 하면 set으로 중복제거 할 때 3,97 과 97,3 을 다른 것으로 인식해서 제거 안함