대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요. (주의: 첫번째 자리가 0이면 대칭수가 아님)
http://euler.synap.co.kr/prob_detail.php?id=36
접근
대칭수인지 검사하는 방법은 고전적으로 양끝에 있는 원소를 비교하고, 두 원소가 같으면 점점 중심쪽으로 한 칸씩 이동하면서 원소를 비교하는 방법이 있다. 이 방법은 길이 L인 배열에 대해서 L / 2 만큼의 비교만하면 되기 때문에 효율이 좋다고 알려져 있다. 하지만 파이썬에서는 for / while 루프의 효율이 별로 좋지 않다. 따라서 이 경우만큼은 정수를 문자열로 변환하는 것이 가장 효율적인 방법이다. (분리한 글자들을 다시 정수로 재변환할 필요가 굳이 없기 때문이다.) 또, 이진수로 변환하기 위해서는 내장 함수인 bin()을 사용하는 것이 가장 좋다. 이 함수는 2진수 리터럴 값을 리턴하므로 앞 두 글자는 제외한 값을 취해야 한다.
def test(n: int) -> bool:
s, b = str(n), bin(n)[2:]
return s == s[::-1] and b == b[::-1]이렇게 십진수와 이진수에서 모두 대칭수인 것을 찾는 함수는 준비가 되었다. 여기서 또 한가지 주목할 점은 이진수에서 첫자리는 항상 1이다. ( ‘010’이라고 쓰지는 않잖아) 따라서 마지막자리가 0인 값은 대칭수가 될 수 없는데, 마지막 자리가 0이라는 말은 짝수라는 것이다. 따라서 홀수에 대해서만 검사하는 것으로 범위를 더 줄일 수 있다.
%%time
print(sum(filter(test, range(1, 100_0000, 2)))
# CPU times: total: 250 ms
# Wall time: 238 ms참고
정수를 각 자리 숫자로 분리할 때, 문자열을 통한 분리와 루프를 통한 분리 중에서 어떤 것이 더 효율적일까?
def digit1(n):
return list(map(int, str(n)))
def digit2(n):
ns = []
while n > 0:
n, r = divmod(n, 10)
ns.append(r)
return ns[::-1]파이썬의 루프가 비효율적임에도 불구하고 문자열을 통한 분리보다는 루프를 도는 것이 더 빠르다.
%timeit digit1(15481)
# 708 ns ± 6.26 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
%timeit digit2(15481)
# 618 ns ± 3.32 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)하지만, 자리 수가 많아져서 루프를 더 많이 돌아야하면 문자열로 처리하는 것이 더 효율적이다.
%timeit digit1(154811548115481154811548115481)
# 3.66 µs ± 132 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
%timeit digit2(154811548115481154811548115481)
# 4.57 µs ± 280 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)