알고리즘 퍼즐 68 - 1

알고리즘 퍼즐 68

1장 - 01 앞뒤가 같은 10진수 만들기

10진수, 2진수, 8진수 그 어느 것으로 표현하여도 대칭수가 되는 수 중, 10진수의 10 이상에서의 최솟값을 구해 보세요.

먼저 아래의 코드처럼 스택과 for문을 사용하여 작성해보았다. 한눈에 봐도 코드가 길고 비효율적이지만 실제로 실행시간을 측정하기 위해 일단 작성해봤다.

import time
start = time.time()
Stack = []
num = 10
while True:
    binnum = str(bin(num));octnum = str(oct(num))
    num = str(num)
    count = 0
    octnum = octnum.replace("0o", "")
    binnum = binnum.replace("0b", "")
    icount = len(octnum)+len(num)+len(binnum)
    for i in range(len(num)):
        Stack.append(num[i])
    for i in range(len(num)):
        if Stack.pop() == num[i]:
            count += 1
    for i in range(len(binnum)):
        Stack.append(binnum[i])
    for i in range(len(binnum)):
        if Stack.pop() == binnum[i]:
            count += 1
    for i in range(len(octnum)):
        Stack.append(octnum[i])
    for i in range(len(octnum)):
        if Stack.pop() == octnum[i]:
            count += 1
    if icount == count:
        print(num,"는 10이상 최소 회문수입니다")
        break
    else: 
        num = int(num) + 1
 end = time.time()
 print(end - start)

위와 같이 코드를 작성하였을때 실행시간은 약 0.006초가 나왔는데, 이를 더 효율적으로 만들기 위해 아래처럼 생각해봤다.

• 10 이상의 10진수에서 회문수는 11,22,33,44,55,66 ....
  형태로 존재한다. 이를 11부터 시작하여 11을 더한 숫자들만 검사하면 좋겠지만 99 이상의 숫자에서는 기존의 규칙이 통하지 않는 문제가 발생한다.

• 2진수에서의 회문수는 일단 가장 오른쪽 수와 가장 왼쪽 수가 둘다 0이거나 1 이어야 한다. 그런데 2진수를 생각해보면 0,1,10,11,100,101,110... 즉, 0으로 시작하는 2진수는 10진수로 0일때만 존재하고 그 외의 모든 경우에서 항상 1로 시작한다. 따라서 10진수로 10 이상인 2진수의 회문수는 1로 시작해 1로 끝나는 경우에만 존재한다. 이는 10진수의 홀수만을 검사하면 된다는 것을 의미한다. 이제 이를 이용해서 다음과 같이 코드를 수정해 보았다.

start = time.time()
num = 11
while True:
    num_10 = str(num)
    num_8 = oct(num).replace("0o","")
    num_2 = bin(num).replace("0b","")
    
    if num_10 == num_10[::-1]\
       and num_8 == num_8[::-1]\
       and num_2 == num_2[::-1]:
           print(num)
           break
    num += 2
    
end = time.time()
print(end - start)

실행결과 약 0.001초가 나왔으며, 또한 반복문을 여러개 작성하지 않고 파이썬 리스트 슬라이싱 기법을 이용하여 간단하게 처리해 더욱 효율적으로 구현하였다.