백준 6757

코드 마무리가 필요한 부분. 

일단 수정한 부분은, 숫자를 n진법으로 썼을 때 자리수가 작은 수들은 체크할 조건은 적지만 survey해야 하는 n의 수가 많아 시간이 오래 걸리는 주범.

3자리수까지는 그냥 search하고 2자리수가 되는 부분은 소인수분해를 이용하면 해결할 수 있다.

따라서 소인수분해를 하고, 특정한 약수를 골라내려 palindrome이 되게 하는 n을 출력하는 방식.

그런데 마지막에 어디선가 작은 수 하나가 튀어나오는데 

카페 닫을 시간이 되어 일단 게시하고 수정하려고 함.

아래는 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int x;
	int[][] primeList=new int[2][11];
	int[] palindromeList=new int[1000];
	int theListIndex=0;
	
	public Main(int x) {
		this.x=x;
	}

	void makePrimeDecompositionList() {
		int index=0;
		int x=this.x;
		for(int i=2;i*i<x;i++) {
			while(x%i==0) {
				if(primeList[0][index]!=i) {
					index++;
					primeList[0][index]=i;
				}
				primeList[1][index]++;
				x/=i;
			}
		}
		if(x!=1) {
			primeList[0][index+1]=x;
			primeList[1][index+1]=1;
		}
	}
	
	void surveyListSmallerThanIndex(int index,int currentNum) {
		if(index==1) {
			for(int i=primeList[1][1];0<=i;i--) {
				if((currentNum*currentNum)<x) {
					palindromeList[theListIndex++]=x/currentNum-1;
					currentNum*=primeList[0][1];
				}
				else {
					break;
				}
			}
		}
		else {
			for(int i=primeList[1][index];0<=i;i--) {
				surveyListSmallerThanIndex(index-1,currentNum);
				currentNum*=primeList[0][index];
			}
		}
	}
	
	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() {
		int i=2;
		for(;i*i*i<x;i++) {
			checkPalindrome(i);
		}
		for(;i*i<x;i++) {
			if(x/(i*i)==x%i) {
				System.out.println(i);
			}
		}
		
		makePrimeDecompositionList();
		int index;
		for(index=1;primeList[0][index]!=0;index++) {}
		surveyListSmallerThanIndex(index-1,1);
		Arrays.sort(palindromeList);
		for(index=0;palindromeList[index]==0;index++) {}
		System.out.println(Arrays.toString(palindromeList));
		for(;index<palindromeList.length;index++) {
			System.out.println(palindromeList[index]);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();
		Main main=new Main(x);
		main.printPalindromeNum();
	}
}