📌 문제 039) 소수 & 팰린드롬 수 중에서 최솟값 찾기
시간 제한 2초, 골드 V, 백준 1747번
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79197과 324423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
31 # N
출력
첫째 줄에 조건을 만족하는 수를 출력한다.
101
1단계 문제 분석
- 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후, 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다.
- 앞에서 배웠던 두 문제와 매우 비슷하므로 답을 쉽게 구할 수 있다.
- 단, 팰린드롬 수를 판별할 때, 숫잣값이 리스트 형태로 적절하게 변환이 가능하다는 점을 이용하면 조금 더 쉽게 로직을 구현할 수 있다.
- 2~10,000,000 사이에 존재하는 모든 소수를 구한다. 그중 N보다 크거나 같은 소수에서 팰린드롬 수인지를 판별한다.
- 소수의 값을 리스트 형태로 변환한 후, 양끝의 투 포인터를 비교하면 쉽게 팰린드롬 수인지 판별할 수 있다.
- 소수 1,030,401을 예로 들어 보자. 리스트 형태로 변환하고, 리스트의 처음과 끝을 가리키는 포인터 (S, E)를 부여해 두 값을 비교한다. 두 값이 같으면 S++, E--연산으로 두 포인터를 이동한다. S < E를 만족할 때까지 반복해 모든 값이 같으면 팰린드롬 수로 판별한다.
2단계 슈도 코드
N(어떤 수)
A(소수 리스트)
for 2 ~ 10000001:
A 리스트 초기화 # 인덱스를 자기 값으로 초기화
for A 리스트 길이의 제곱근으로 반복:
소수가 아니면 넘어감
for 소수의 배수 값을 10000001까지 반복:
현재 수가 소수가 아니라는 것을 표시
# 팰린드롬 판별 함수 구현
팰린드롬 함수:
숫잣값을 리스트 형태로 변환
s(시작 인덱스), e(끝 인덱스)
while s < e:
만약 시작과 끝 인덱스에 해당하는 값이 다르면 return false
s값 증가
e값 증가
반복문을 다 돌았으면 return true
while true:
N부터 값을 1씩 증가시키면서 A[i]값이 소수이면서 팰린드롬 수인지 판별
맞으면 반복문 종료3단계 코드 구현
import math
N = int(input())
A = [0] * (10000001)
for i in range(2, len(A)):
A[i] = i
for i in range(2, int(math.sqrt(len(A)) + 1)): # 제곱근까지만 수행
if A[i] == 0:
continue
for j in range(i + i, len(A), i): # 배수 지우기
A[j] = 0
def isPalindrome(target): # 팰린드롬 수 판별 함수
temp = list(str(target))
s = 0
e = len(temp) - 1
while (s < e):
if temp[s] != temp[e]:
return False
s += 1
e -= 1
return True
i = N
while True: # N부터 1씩 증가시키면서 소수와 팰린드롬 수가 맞는지 판별
if A[i] != 0:
result = A[i]
if (isPalindrome(result)):
print(result)
break
i += 1📌 문제 040) 제곱이 아닌 수 찾기
시간 제한 2초, 골드 I, 백준 1016번
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 '제곱이 아닌 수'라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 '제곱이 아닌 수'가 몇 개 있는지 출력한다.
입력
첫째 줄에 두 정수 min과 max가 주어진다.
1 10 # min max
출력
첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.
7
1단계 문제 분석
- 언뜻 보면 min의 최댓값이 1,000,000,000,000으로 매우 큰 것 같지만, 실제로는 min과 max사이의 수들 안에서 구하는 것이므로 1,000,000의 데이터만 확인하면 된다.
- 제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별 로직에 적용해 문제를 해결해보자.
- 2의 제곱수인 4부터 max값인 10까지 제곱수를 찾는다.
- 탐색한 리스트에서 제곱수로 확인되지 않은 수의 개수를 센 후 출력한다.
- 데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색해 시간 복잡도를 최소화하는 것이 이 문제 풀이의 핵심이다.
2단계 슈도 코드
Min(최솟값) Max(최댓값)
Check(Min~Max 사이에 제곱수 판별 리스트
for i = 2 ~ Max의 제곱근:
pow(제곱근)
start_index(최솟값/제곱근) # 나머지가 있는 경우 1을 더한다.
for j = start_index ~ Max 사이 반복: # 제곱수의 배수 형태로 탐색
j * pow가 Max보다 작을 때 최솟값, 최댓값 사이의 제곱수이므로
Check 리스트에 저장
count(제곱이 아닌 수 카운트)
for 0 ~ Max - Min:
Check 리스트에서 제곱이 아닌 수라면 count 증가
count 출력3단계 코드 구현
import math
Min, Max = map(int, input().split())
Check = [False] * (Max - Min + 1)
for i in range(2, int(math.sqrt(Max) + 1)):
pow = i * i
start_index = int(Min / pow)
if Min % pow != 0:
# 나머지가 있는 경우 1을 더해 Min보다 큰 제곱수에서 시작하도록 설정
start_index += 1
for j in range(start_index, int(Max / pow) + 1): # 제곱수를 True로 변경
Check[int((j * pow) - Min)] = True
count = 0
for i in range(0, Max - Min + 1):
if not Check[i]:
count += 1
print(count)
안녕하세요 :)