[Algorithm] 백준 1929

문제

문제

처음 내가 생각한 코드

import sys

m, n = map(int, sys.stdin.readline().split())


for i in range(m, n+1):
    count = 0
    if i == 1:
        continue
    for j in range(2, int(i ** 0.5)+1):
        if i % j == 0:
            count += 1
            if count == 1:
                break;
    if count == 0:
        print(i)

맞았다 분명 맞았는데 찝찝하다 난생처음 보는 시간이다 6256ms 

나는 어떻게 이 시간을 줄일 수 있을까 생각하다 도저히 모르겠어서 다른 사람의 답을 보았다

 

그렇다..... 답을 봐 버렸다 하지만 내 마음속은 시원했다

양심의 가책이 느껴진다 

 

다른 사람의 코드 

def prime(s, e):
    arr = [False, False] + [True] * (e + 1)
    t = int(e ** 0.5)+1
    for i in range(2, t):
        if arr[i]:
            for j in range(i+i, e, i):
                arr[j] = False
    return [n for n in range(s, e) if arr[n]]

s, e = map(int, input().split())
for i in prime(s,e):
    print(i)

나는 이걸 보고 어떻게 이런 생각을 했지 라는 생각을 하였다

 

평소 나는 배열을 만들어서 문제를 풀면 시간이 정말 오래 걸릴 것이다 라는 생각을 했다 하지만 이 문제를 보고 그딴 생각을 접었다

 

이 코드가 빠른 이유

1. 배열의 0, 1을 먼저 False로 만들고 나머지 배열의 크기에 맞게 True로 초기화시킨다

2. 그리고 2부터 자기 자신을 제외한 배수들을 모두 False로 바꿔준다

 

위 의 두 가지 덕분에 빠른 것 같다는 생각을 했다

 

진짜 어떻게 이런 생각을 할까

 

 

배울 점

1. 문제를 풀 때 상황에 맞게 배열을 활용할 수 있도록 하자

2. 한 문제에 정말 다 영한 풀이가 있다 넓게 생각하자