이번문제는 주어진 조건에서 가장 큰 Palindrome을 찾는 문제입니다. 그럼 문제를 풀기에 앞서서... Palindrome이 뭔지 한번 알아볼까요??
Palindrome이란?? 문자열이던 숫자열이던 주어진 값의 중간에 거울을 대었을때, 완벽하게 대칭이 되는 상황을 말합니다.
그림으로 보면 다음과 같이 양끝의 m이 대칭되고, 그 안으로 순서대로 o, l 이 대칭이 됩니다. 짝수인 경우는 전체가 대칭인 상황이고, 홀수인경우는 가장중앙을 기준으로 대칭이 되게 됩니다.
그럼 다시 문제로 돌아가서... 이번 문제는, 2개의 3자리수 숫자의 곱으로 표현되는 수의 집합중에 가장 큰 수를 고르는 문제입니다. 그럼 찬찬히 해당 문제를 저는 이렇게 풀겠습니다.
- 조건 확인 : 3자리수 2개의 곱으로 표현되는 수는 100 x 100 ~ 999 x 999 까지의 수 (10,000 ~ 998,001)
- 주어진 수가 Palindrome인지 판별하는 로직
- Palindrome인 수가 3자리수의 수 2개의 곱으로 구성되는지 판별하는 로직
이렇게 단계만 된다면 구할 수 있겠죠??
1. 주어진 수가 Palindrome인지 판별하는 로직
우선 판별대상이 되는 숫자를 강제로 문자열로 변환합니다. 이는 각 자리수 별로 쉽게 동일한지 아닌지를 판단하기 위함입니다. 사실 자리수를 구하기 위해서 1, 10, 100, 1000, 10000 등으로 나눠도 구할 수는 있지만 여간 불편한게 아니죠?? 편하게 문자열로 변경 후 문자열 길이를 구해서 a[1]과 같이 바로 접근해서 확인해주면 편하니까요.
def searchP(target):
check = str(target)
size = len(check)
to = size//2
res = True
for i in range(to):
if(check[i]!=check[size-i-1]):
res = False
if(res==False): break
return res길이를 구하고, 짝수 홀수 상관없이 2로 나눈 몫의 위치까지만 앞/뒤 위치로 구분해 주면 됩니다.
코드에서 보면 check[i]가 앞위치... check[size-i-1]이 뒤의 위치가 되겠네요~
2. Palindrome인 수가 3자리수의 수 2개의 곱으로 구성되는지 판별하는 로직
Problem3에서 볼수있지만, 왠만한 수학문제에서 loop를 구현한다면 대부분 sqrt()에 해당하는 수까지 돌게 됩니다. 그 이후는 불필요한 반복이 되기 때문에 동작시간만 들어나고 결과는 이미 나와있는 상황이 되지요. 역시나 이번에도 3자리수의 곱을 판별하기위해서 sqrt()를 구한 후, 그 역순으로 나눠나가도록 하겠습니다.
그 상황에서 나눠지고 1000보다 작은 수가 된다면 그게 답이 되겠죠??
def checkDiv(target):
fr = int(mt.sqrt(target))
res = False
for i in range(fr,0,-1):
a,b = divmod(target,i)
if b == 0:
if a > 1000:
break
else:
res = True
break
return res3. 최종코드
해당 문제의 범위는 (10,000 ~ 998,001) 입니다. 당연히 가장 큰 수를 구하는 문제이기 때문에 998,001부터 순회를 돌면 되겠습니다.
import math as mt
def searchP(target):
check = str(target)
size = len(check)
to = size//2
res = True
for i in range(to):
if(check[i]!=check[size-i-1]):
res = False
if(res==False): break
return res
def checkDiv(target):
fr = int(mt.sqrt(target))
res = False
for i in range(fr,0,-1):
a,b = divmod(target,i)
if b == 0:
if a > 1000:
break
else:
res = True
break
return res
if __name__ == '__main__':
tc = int(input())
for i in range(tc):
target = int(input()) -1
ans = 1
for i in range(target,0,-1):
if(searchP(i)):
if(checkDiv(i)):
ans = i
break
print(ans)2
101110 결과는 : 101101
800000 결과는 : 793397
이렇게 나오고, Level5로 넘어가게 됩니다.
-Ayotera Lab-
댓글