728x90
문제 (링크)
https://www.acmicpc.net/problem/4948
나의 풀이
첫 번째 풀이
import sys
import math
data = []
while True:
n = int(sys.stdin.readline())
# 입력값이 0이 아닐때까지 입력값을 data배열에 저장
if n == 0:
break
else:
data.append(n)
def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리턴해주는 함수
arr = [True for _ in range(y+1)]
arr[1] = False
for i in range(2, int(math.sqrt(y)) + 1):
if arr[i]:
j = 2
while i * j < y:
arr[i*j] = False
j += 1
count = 0
for i in range(x, y):
if arr[i]:
count += 1
return count
for x in data:
print(is_prime_count(x+1, x*2+1)) # x보다 크고 2x보다 작거나 같은 값 사이의 소수의 개수
가장 기본적인 에라토스테네스의 체 알고리즘을 이용해 문제를 해결하였다.
문제가 n초과 2n이하의 숫자들 사이의 소수의 개수를 출력하는 것이었는데, n이상으로 착각을 해서 계속 실패판정이 났었다.
문제를 잘 읽자..
위 코드로도 성공을 했지만, 풀고나서 한 가지 생각이 들었다.
어차피 arr[i]는 숫자 i가 소수인지 아닌지를 저장해주는 배열인데, 이걸 굳이 매번 함수를 돌릴 때마다 초기화했다가 다시 채워줄게 아니라, 입력 범위 내의 모든 숫자들에 대한 arr[i] 값을 구해놓고 입력값에 대해 갯수만 세면 훨씬 더 효율적일거란 생각이 들었다.
따라서 그러한 방식으로도 코드를 작성해봤다.
두 번째 풀이
import sys
import math
data = []
while True:
n = int(sys.stdin.readline())
if n == 0:
break
else:
data.append(n)
# 입력 n의 범위는 1 <= n <= 123456 이므로, 2n의 값까지 y를 설정
y = 123456 * 2
arr = [True for _ in range(y+1)]
arr[1] = False
for i in range(2, int(math.sqrt(y))+1):
if arr[i]:
j = 2
while i * j <= y:
arr[i*j] = False
j += 1
for x in data:
count = 0 # data의 각 값들에 대한 count 초기화
for i in range(x+1, 2*x+1): # x초과 2x이하까지 i가 돈다
if arr[i]: # arr[i]가 True면 (소수이면)
count += 1 # 카운트에 1 추가
print(count)
입력값으로 들어오는 n 은 1 이상 123456 이하이므로, 최대 범위가 될 수 있는 값은 2n일 경우의 123456 * 2이다.
따라서, arr를 123456 * 2의 범위만큼 설정해주고 소수 여부를 처리해줬다.
이후, data의 값들을 돌면서 x 초과 2x 이하에 대한 count를 계산해주는 방식을 거쳤다.
두 풀이 모두 통과판정을 받았지만, 걸린 시간 차이가 6배로, 엄청난 시간적 차이를 보였다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 1806번 부분합 - 파이썬(Python) (0) | 2021.02.02 |
---|---|
[백준] 2003번 수들의 합2 - 파이썬(Python) (0) | 2021.02.01 |
[백준] 1929번 소수 구하기 - 파이썬(Python) (0) | 2021.01.31 |
[백준] 1463번 1로 만들기 - 파이썬(Python) (6) | 2021.01.26 |
[백준] 1978번 소수 찾기 - 파이썬(Python) (1) | 2021.01.26 |