Palindromic Numbers ( ACM-ICPC 교내 예선 )

ACM-ICPC 예선전으로 교내 대회를 열었는데, 이들 중 푼 문제들을 포스팅하겠다. 지금 처음 포스팅 하는 이 문제가 제일 짧아서 쓰긴하는데 이거 받아쓰는게 코드 받아적는 것보다 더 오래 걸릴 것 같다. 참고로 ACM-ICPC는 C,C++,JAVA 만 허용하기 때문에 내 주언어인 파이썬으로 못 짰다. 덕분에 실제 대회에서는 아-주 고생했다만 여기서는 좀 편하게 해답 알고리즘을 공유할 수 있을 것이다.

[문제]

어떤 숫자를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 숫자를 회문 (palindrome)인 숫자라고 한다. 예를 들어, 747은 회문인 숫자이다. 255도 회문인 숫자인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력 받았을 때, 이 숫자가 어떤 B 진법 (2<=B<=64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 숫자의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다.

[입력]

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64이상 1,000,000 이하인 하나의 정수로 주어진다.

[출력]

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 답을 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 주어진 수가 어떤 B진법 (2<=B<=64)으로 표현하여 회문이 될 수 있다면 1을, 그렇지 않다면 0을 출력한다.

[예시]

입력	출력
3 747 255 946734	1 1 0

def base_converter( num, base ):
    lst = list()
    while num > 0:
        lst = [ num%base ] + lst
        num /= base
    return lst
 
def is_palindrome( arr ):
    for i in xrange( len(arr)/2 ):
        if arr[ i ] != arr[ -(i+1) ] :
            return False
    return True
 
T = input()
for _ in xrange( T ):
    num = input()   # input number
 
    flag = False    # palindrome check
    base = 64       # initial base radix
    while base > 1 and not flag:
        flag |= is_palindrome(base_converter( num, base ))
        base -= 1
        
    if flag:
        print 1
    else:
        print 0
 

시간이 되면 C 코드 정도는 짜볼 수 있을 거 같긴 한데 무튼 위에 있는건 파이썬 코드다. 필요한 기능들을 함수 단위로 구분해서 구현해봤다. 

def base_converter( num, base ):
    lst = list()
    while num > 0:
        lst = [ num%base ] + lst
        num /= base
    return lst
 

처음 필요한건 10진법 숫자를 입력받아서 B진법으로 바꾸어 표현할 수 있어야한다. 문제에서 B가 64까지 될 수 있으므로 0~9 (10개) , A~Z (26개) 까지 다써도 각 자리수 숫자들 (64개) 을 표현할 문자가 부족하므로 숫자 개별적으로 (digit by digit) 으로 확인하긴 힘들다. 따라서 각 자리수 별로 숫자를 계산해서 그대로를 원소로 만들어 저장하는 list로 표현하기로 했다. 지난 글 ( Link ) 에서 문자열로 반환했었던 함수를 이번엔 list로 반환하는 것으로 바꾼것이니 거의 비슷하다. list 그 자체 반환하게 되는 것에 주의하자.

def is_palindrome( arr ):
    for i in xrange( len(arr)/2 ):
        if arr[ i ] != arr[ -(i+1) ] :
            return False
    return True
 

회문 검사를 하는 함수도 필요하다. list를 받아서 바깥 양끝의 원소가 서로 같은지 다른지를 안쪽으로 따져가면서 검사하고 그 결과를 반환하면 된다. 한가지 팁이 있다면 총 원소 개수가 홀수냐 짝수냐를 따질 필요가 없다.

다른 언어를 사용하는 사람들을 위해 팁을 주자면 진법 변환의 결과를 꼭 정확한 순서대로 저장할 필요는 없다. 4번째 줄에서 보면 원소를 앞부분에서 합치고 ( concatenation ) 있는데 이는 append 메소드를 이용하고서 뒤집는 ( reverse ) 시간 낭비를 없애기 위함이다. C에서는 위 같은 list concatenation이 자유롭지 못하기 때문에 그냥 순서대로 배열에 저장시켜도 된다. 왜냐하면 이 프로그램은 회문 검사가 목적이기 때문이다. 회문인지 아닌지, 앞뒤로 같은 원소를 가지고 있는지 아닌지만 알면 되기 때문에 굳이 뒤집는 과정에서 시간 낭비를 할 필요없다. 저 위에 구현시킨 것도 아마 컴파일 시켜놓으면 차이가 날텐데, lst를 매번 새로 만들고 있기 때문에 그냥 append만 시키는 것이 시간적으로는 더 좋을 것이다.