백준 2581번 - 소수 (PYTHON 풀이)

문제:

 

해당 문제는 두 수를 입력받고 두 값 사이에서 소수를 찾아 전부 더한 값과 가장 최솟값을 출력하는 문제이다.

 

풀이:

a=int(input())
b=int(input())
k=[]

for i in range(a,b+1):
    num=0
    for j in range(1,i+1):
        if i % j == 0:
            num+=1
    if num == 2:
        k.append(i)

if k:
    print(sum(k))
    print(min(k))
else:
    print(-1)

초기 답안은 이렇게 작성하였다. 비쥬얼스튜디오에서 실행 시 이상없이 잘 출력이 되었는데 백준에서는 자꾸 시간초과가 발생하였다.

우선 어제 업로드한 문제에서 num 변수를 받아 이 값이 2인 수를 약수라고 판단하고 그 수를 리스트에 추가하였다. 이를 활용하여 오늘 문제도 비슷한 방식으로 소수를 판별한 뒤 전체 합친 값과 최솟값을 출력하였는데 이 과정에서 시간초과가 발생하는 것 같았다.

 

import sys

m = int(sys.stdin.readline())
n = int(sys.stdin.readline())
num = []
for i in range(m, n+1):
    if i > 1:
        c = 0
        for j in range(2,i):
            if i % j == 0: 
                c += 1
                break
        if c == 0:
            num.append(i)

if len(num) == 0:
    print('-1')
else:
    print(sum(num))
    print(min(num))

수정한 코드는 다음과 같다. 처음 코드와 크게 달라진 것은 우선 0,1은 소수가 아니므로 처음부터 1 초과인 수부터 검사를 하는 것, 그리고 1과 자기 자신은 무조건 나눠 떨어지기 때문에 두번째 for문에서 2부터 i-1까지 범위를 줄인 것이다. 아, 그리고 시간 초과를 해결해줬다고 생각한 핵심 코드는 break이다. c가 1이라도 올라가는 순간 그것은 소수가 아닌 게 되기 때문에 'c += 1' 다음에 break를 넣었다.

이렇게 하면 문제에서 원하는 방향으로 풀이도 되고 시간 초과 문제도 해결된다!

(추가: import sys는 input으로 한 줄씩 입력받을 때보다 속도가 훨씬 빠르기 때문에 속도를 줄이기 위해선 해당 라이브러리를 임포트 해야한다. input은 개행 문자를 제거하는 과정을 거치기 때문에 sys.stdin.readline()보다 더 느리다!)

.

.

.

이전 문제에서는 num이 2가 되는 순간을 소수로 판단하고 코드를 작성했는데 이번 문제는 오히려 자기 자신과 1로 나누는 과정을 배제하고 0이 되는 수를 소수라고 판별하여 복잡도를 낮추었다. 분명 .. 자료구조에서 시간복잡도를 배웠지만.. 코드에서 활용하는 것은 어려운 일이다 .....