백준 6757 Palindrome Number

예를 들어, 10진법에서 9는 다음과 같이 작성할 수 있다.

16진법으로는 9

8진법으로는 11 (1×81 + 1×80 = 9)

2진법으로는 1001 (1×23 + 0×22 + 0×21 + 1×20 = 9)

9는 위의 세가지 진법에서 모두 팰린드롬이다. 팰린드롬이란, 순서를 반대로 했을 때, 원래 순서와 같은 수열을 의미한다. 영단어에서 팰린드롬은 "dad", "mom", "racecar"가 있다. 9, 11, 1001과 같은 숫자도 팰린드롬이다.

10진법 숫자 X가 주어졌을 때, b진법으로 나타냈을 때, 팰린드롬인 것의 개수를 구하는 프로그램을 작성하시오. (2 ≤ b < X)

INPUT: 첫째 줄에 X가 주어진다. $(2\leq X \leq 1,000,000,000)$

OUTPUT: X를 b진법으로 나타냈을 때, 팰린드롬인 것을 모두 한 줄에 하나씩 증가하는 순서대로 출력한다.

그냥 모든 값을 다 대입하여 palindrome이 되는 경우를 골라내었다. 시간 내에 해결이 가능하기는 하지만 역시 $10^9$정도의 수를 다루는 만큼 시간제한에 아슬아슬하게 걸린다.

조금 더 나은 알고리즘을 작성하는 중인데 어디선가 뜬금없는 숫자가 튀어나와 정리하는 중.

아래는 단순한 로직으로 짠 오래 걸리는 코드.

import java.util.Scanner;

public class Main {
	int x;
	
	public Main(int x) {
		this.x=x;
	}
	
	void checkPalindrome(int b) {
		int digit=0;
		int[] numeralDigitList=new int[30]; //if binary, number of digits cannot exceed 30
		boolean isPalindrome=true;
		for(int i=x, index=0;i!=0;i=(i/b),digit++) {
			numeralDigitList[index++]=i%b;
		}
		for(int i=0;i<digit/2;i++) {
			if(numeralDigitList[i]!=numeralDigitList[digit-1-i]) {
				isPalindrome=false;
				break;
			}
		}
		if(isPalindrome) {
			System.out.println(b);
		}
	}
	
	void printPalindromeNum() {
		for(int i=2;i<Math.sqrt(x);i++) {
			checkPalindrome(i);
		}
		for(int i=(int)(Math.sqrt(x));i<x;i++){
			if((x/i)==(x%i)) {
				System.out.println(i);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();
		Main main=new Main(x);
		main.printPalindromeNum();
	}
}