프로젝트 오일러 004

대칭수

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수라고 합니다. 어떤 정수 N이 대칭수인지 알아보려면 각자리 숫자의 리스트로 분해한 후, 그 리스트가 대칭인지를 보면 됩니다. 가장 간편한 방법은 reversed를 사용해서 뒤집은 리스트와 원래의 리스트가 같은지를 보면 됩니다.

그러나 이 문제에서는 이런 연산을 아주 많이 해야 합니다. 따라서 빠른 시간 내에 답을 찾는 코드를 작성하려면 이 연산에 드는 시간을 최소화할 필요가 있습니다. 경험적으로 가장 빠른 방법은 정수를 문자열 s로 변환한 후,이 문자열을 뒤집은 것이 같은지 체크하는 것입니다.

세 자리 정수 2개를 선택하는 방법은 810만 가지가 있지만, a × b = b × a 이므로 뒤에 있는 수가 같거나 더 큰 경우만 생각하면 루프의 횟수를 절반으로 줄일 수 있습니다.

ispal = lambda n: str(n) == ''.join(str(n)[::-1])
pals = set()

for x in range(100, 1000):
	for y in range(y, 1000):
		z = x * y
		if ispal(z):
			pals.add(z)

print(max(pals))

다른 접근

이렇게 간단하게 풀 수 있지만 다른 접근법을 생각해볼 수도 있습니다. 위 풀이는 모든 대칭수를 찾은 후에 가장 큰 값을 찾았습니다. 반대로 가장 큰 수부터 거꾸로 내려오면서 대칭수를 찾는다면 어떨까요? 그리고 그 대칭수가 세자리 자연수 두 개의 곱으로 표현되는지를 찾는 것입니다. 언뜻 생각하기에는 상당히 비효율적일 것 같지만, 조건에 맞는 답을 하나만 찾는다면 그 값이 최대값임이 분명하기 때문에, 결과적으로는 더 빠르게 종료할 수 있습니다.

def check_number(n: int) -> bool:
	for m in range(100, int(n**0.5 + 1)):
		x, y = divmod(n, m)
		if y == 0 and 99 < x < 1000:
			return True
	return False

for x in range(999_999, 10000, -1):
	if ispal(x) and check_number(x):
		print(x)
		break

어떤 수가 세자리 자연수 두 개의 곱인지를 찾는 방법은, 100부터 N의 제곱근 사이의 정수로 나눠보고, 나눌 수 있는 경우 그 몫 역시 100~999 범위에 있는지를 검사하면 됩니다.