[algorithm] 백준 4948 - 베르트랑 공준

[algorithm] 백준 4948 - 베르트랑 공준

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 4948번 문제 - 베르트랑 공준 에 대한 풀이를 살펴보도록 하겠습니다.

 

저번에 살펴본 문제들과 푸는 방식은 비슷하니까 잘 풀어봅시다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제와 풀이를 다함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 4948

 

https://www.acmicpc.net/problem/4948

 

4948번: 베르트랑 공준

 

문제 해석

 

문제에서 원하는 것은 주어지는 자연수 n에 대하여 n보다는 크고 2n보다는 작거나 같은 범위안에

소수가 몇개 존재하는가 입니다.

소수를 찾기위해 에라토스테네스의 체를 사용하거나 시간 단축을 위해 범위를 제곱근까지만 찾는다거나 하는

테크닉을 앞선 문제에서 사용했었습니다.

오늘도 소수관련 문제이니만큼 위와 같은 방법을 사용해 문제를 해결해봅시다.

 

풀이 1 - 시간초과

 

while True:
    n = int(input())
    count = 0
    
    if n == 0:
        break
    else:
        for i in range(n + 1, n*2 + 1):
            prime = True
            for j in range(2, int(i ** 0.5) + 1):
                if i % j == 0:
                    prime = False
                    break
            if prime == True:
                count += 1
        print(count)

 

풀이 2 - 통과

 

def isPrime(x):
    if x == 1:
        return False
    elif x == 2:
        return True
    else:
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True

num_list = list(range(2, 123456 * 2))
primes = []

for i in num_list:
    if isPrime(i):
        primes.append(i)

while True:
    n = int(input())
       
    if n == 0:
        break
    
    count = 0
    
    for i in primes:
        if n < i <= n*2:
            count += 1
    print(count)

 

풀이 해석 및 팁

 

풀이 1의 코드를 백준에 제출하면 시간초과라는 결과를 받게됩니다.

소수를 구하는 범위에 제곱근을 이용해서 시간단축을 도모했지만 그래도 시간초과가 발생해버렸습니다.

문제에서 주어지는 자연수의 범위가 1 ≤ n ≤ 123456 인 것을 보고 아예 범위에 존재하는 소수를 미리 파악해두고

그 정보를 사용해 문제가 원하는 범위에 속하는 소수의 개수를 출력하도록 수정한 코드가 풀이 2의 코드입니다.

이렇게 코드를 수정하고 제출을 해보면 시간초과가 사라지고 통과를 받게 됩니다.

---

여기까지 백준 4948 번 - 베르트랑 공준 의 풀이였습니다.

 

소수 판별 검사를 할 때 제곱근을 사용해 범위를 줄이는 것까지 신경썼지만 시간초과를 받았습니다.

 

어떻게 더 시간을 줄일 수 있을까 고민하다가 풀이 2와 같은 방법을 통해 문제를 해결할 수 있었습니다.

 

도출되는 답은 같아도 그 안에서 돌아가는 과정은 다를 수 있습니다.

 

우리 모두 효율적인 흐름을 가진 코드를 짜려고 노력하는 습관을 들여봅시다.

 

감사합니다.