오일러 프로젝트의 네 번째 문제는 대칭수와 관련된 문제이다. 대칭수는 139931 과 같이 앞에서부터 읽었을 때나 뒤에서부터 읽었을 때 같은 모양이 되는 수를 말한다. 문제는 다음과 같다.
앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
접근
대칭수는 앞에서부터 읽거나 뒤에서부터 읽었을 때가 같은 수이다. 이는 다시 말하면 숫자를 뒤에서 앞으로 뒤집었을 때에도 원본과 같은 내용이 된다는 것이다. 즉 정수를 문자열로 변환한 후, 이를 뒤집어서 원본과 같은지 판단하면 된다. 참고로 세자리 수 두 개를 곱해서 최대 대칭수를 찾을 때 두 수 a, b를 100~999 범위에서 찾기보다는 그 상위 절반인 555~999에서만 찾아도 답을 찾을 수 있다. 이를 통해서 범위를 많이 줄일 수 있다.
풀이
대칭수인지 판별하기 위해서는 문자열을 뒤집어서 판단하는 방법이 있는데, 문자열을 뒤집는 방법은 보통 다음과 같이 쓴다.
a = abc
b = ''.join(list(reversed(a)))reversed 함수를 쓰면 연속열을 뒤집어서 각 원소를 내놓는 제너레이터를 얻게 되는데, 이를 사용해서 리스트를 만들고 다시 ''.join() 을 써서 하나의 문자열로 합치는 것이다. 하지만 파이썬에서 문자열을(뿐만 아니라 모든 연속열에 대해서) 뒤집는 가장 빠른 방법은 슬라이스 문법을 이용하는 것이다.
def is_palindrome(s):
return s == s[::-1]이중 루프를 돌지 않고, 555~999에서 2개 수를 뽑는 중복 조합 내에서 숫자를 뽑고, 그 중에서 최대값을 구한다.
from itertools import combination
def p004():
print(max( x * y for x, y in combinations(range(555, 1000), 2) \
if is_palindrom(str(x * y))))보너스 – Swift 풀이
Swift에서 문자열은 비교적 다루기 무거운 데이터 타입 중 하나이다. 하지만 이 문제에서는 최장 6자리 문자열을 뒤집어서 판단하는 부분이니, 다음과 같이 구현해볼 수 있겠다.
// 회문인지 여부를 검사하는 기능을 문자열을 확장해 넣는다.
extension String {
var isPalindrome: Bool {
return self == String(self.reversed())
}
}
func p004() {
var result = 0
for x in 555...999 {
for y in 555...999 {
let z = x * y
if "\(z)".isPalindrome, x > result {
result = x
}
}
}
print(result)
}문자열을 뒤집고 이를 다시 문자열로 생성해서 원본과 비교하는 것보다는 첫글자와 끝글자, 두 번째 글자와 끝에서 두 번째 글자…를 비교하는 것이 좀 더 빠르다. 이는 다음과 같이 구현한다. (이전에는 advance 함수를 이용했지만, Swift3 부터는 이 함수가 없어졌고, 문자열의 인덱스를 구하는 String.index(_: offsetBy:) 를 이용한다.
extension String {
var isPalindrome: Bool {
for i in 0..<(count / 2) {
if self[index(startIndex, offsetBy: i) !=
self[index(endIndex, offsetBy: (i+1) * -1)]
{ return false }
}
return true
}
}이걸 사용하면 이 문제 한정으로 약 2~3배 가량 빨라지는 듯 하다.