11068 : 회문인 수

문제

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

입력

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

출력

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

예제 입력 1 복사

3
747
255
946734

예제 출력 1 복사

1
1
0

 

• 풀이

 

입력받은 수를 진법변환해서 뒤집어도 같으면 되는 문제

 

2~64로 진법변환해서 가능한 경우 하나라도 있으면 회문이다

 

1~9까지는 그냥 숫자로 변환해도 문제가 없었지만

10 부터는 진법으로 표현한 결과가101110 일때 뒤집으면 011101이 되서 숫자로는 판별이 안됬다

11~64 진법은 문자로 표현하는 방식으로 회문을 구해서 문제를 풀었다

 

import java.util.*;
import java.io.*;

class Main {
    public static int pal(int tmp){
        int res = 0;
        for(int i = 2; i <= tmp && i <= 64; i++){
            StringBuilder sb = new StringBuilder();
            int cur = tmp;
            while (cur != 0){
                int append = cur % i;
                // 10 넘어가면 뒤집을때 문자로 변환해줘야됨
                if (i >= 10){
                    append += 65;
                    while (append-i >= 65 && append-i <= 97) append -= i;
                    sb.append((char)append);
                }
                else sb.append(cur % i);
                cur /= i;
            }
            String s1 = sb.toString();
            String s2 = sb.reverse().toString();
            if (s1.equals(s2)){
                res = 1;
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        while(n --> 0){
            int tmp = Integer.parseInt(br.readLine());
            if (String.valueOf(tmp).equals(sb.append(String.valueOf(tmp)).reverse().toString())) System.out.println(1);
            else System.out.println(pal(tmp));
        }
    }
}