백준 1990 - 소수인팰린드롬
문제
https://www.acmicpc.net/problem/1990
풀이
해당 범위 안에 소수를 찾고 그 소수 집단 중에서 팰린드롬(앞으로 읽으나 뒤로 읽으나 같은 문자열)인 수를 찾는 문제,
문제를 풀기 위해서는
- 팰린드롬을 찾는 방법
- 소수를 확인하는 방법
두 가지 방법을 이용하여 정답을 출력해야한다.
팰린드롬 찾기
파이썬에서 팰린드롬을 확인만 하는 방법은 의외로 간단하다.
파이썬에서는 리스트의 역순이나, 문자열의 역순을 만드는 방법이 매우 간단하다.
test1 = [1,2,3]
test1_reverse = test1.reverse()
test2 = "this is test"
test2_reverse = test2[::-1]이번 문제에서 팰린드롬의 확인은 이러한 방법을 사용하였다.
소수를 찾는 방법
소수를 찾는 방법에는 여러가지 방법이 있지만 두 가지 방법을 기록한다.
1. 약수를 이용한 소수찾기
기본적으로 소수는, 1과 자기자신을 제외하고는 나누어 떨어 질 수 없는 수이다.
그렇다면 찾고자 하는 수의 약수를 찾으면 그 수는 소수가 아니다.
자연수의 약수는 일정한 규칙을 가지기 때문에 판별하고자 하는 수의 제곱근을 이용하여 소수를 판별 할 수 있다.
def prime_number(x):
result = []
for i in range(2,int(math.sqrt(x))+1):
if x % i == 0:
return False
return True이 방법을 이용하여 소수를 찾는다면 O(N^0.5)만에 소수를 판별 할 수 있다.
해당 방법을 이용한 소스코드
import sys, math
a, b = map(int,sys.stdin.readline().split())
result = []
def prime_number(x):
result = []
for i in range(2,int(math.sqrt(x))+1):
if x % i == 0:
return False
return True
for i in range(a,b+1):
if prime_number(i):
if ''.join(list(str(i))[::-1]) == str(i):
result.append(i)
for i in result:
print(i)
print(-1)이 방법의 시간 복잡도는 대략 O(N^1.5)로 추측한다.
결과
2. 에라토스테네스의 체 방법 이용
1번의 방법은 문제에서 요구하는 시간내에 문제를 해결하지 못했다.
그렇다면 약수를 이용한 소수 판별 방법은 정답보다 느린 속도를 가진다.
또다른 방법으로 에라토스테네스의 체 방법을 이용하여 문제를 해결해본다.
에라토스테네스의 체 방법은 1부터 찾고자 하는 수 까지 배열을 가지고 2부터 N^0.5까지 수가 나누어 떨어지면 해당 배열의 원소를 삭제하고 이때 자기 자신은 신경쓰지않는다.
import sys, math
a, b = map(int,sys.stdin.readline().split())
result = []
def prime_numbers(n):
arr = [i for i in range(n+1)] # 인덱싱을 수월하게 하기 위해 0부터 배열 선언
end = int(n**(1/2))
for i in range(2, end+1):
if arr[i] == 0: # 이미 소수가 아님이 판별된 수는 건너뜀
continue
for j in range(i*i, n+1, i): # 자기 자신을 제외한 i의 배수는 모두 0으로 처리함.
arr[j] = 0
#여기서 팰린드롬 수 인지 아닌지 파악하는 로직이 들어감
#팰린드롬: 파이썬 구조상에서는 reverse 또는 역순조회를 이용하여 원본과 같은지 비교!
return [i for i in arr[2:] if arr[i] and (str(arr[i])[::-1] == str(arr[i])) and (a <= arr[i] <= b)]
for i in prime_numbers(b):
print(i)
print(-1)에라토스테네스의 체의 시간복잡도는 O(Nlog(logN))이 소요되고, 일반 약수를 이용한 소수찾기보다 한번에 더 많은 소수를 찾아 낼 수 있으므로 조금 더 효율적이라 볼 수 있다.
하지만 메모리 초과가 떴다... 무엇이 문제일까?
최종 해결
결론은 에라토스테네스의 체를 이용한 문제 풀이까지는 맞았다. 여기서 더 진행하는게 어려워서 해설을 참고하였는데, 10,000,000부터 입력의 최댓값인 100,000,000 까지는 소수 팰린드롬이 없다고한다. 그래서 b의 값이 천만이 넘을 때 천만으로 조정해주고 문제를 풀 때 해결 할 수 있었다.
import sys
a, b = map(int,sys.stdin.readline().split())
def prime_numbers(n):
if n > 10000000:
n = 10000000
arr = [i for i in range(n+1)]
end = int(n**(1/2))
for i in range(2, end+1):
if arr[i] == 0:
continue
for j in range(i*i, n+1, i):
arr[j] = 0
return [i for i in arr[2:] if arr[i] and (str(arr[i])[::-1] == str(arr[i])) and (a <= arr[i] <= b)]
for i in prime_numbers(b):
print(i)
print(-1)
