BOJ11068 회문인수

https://www.acmicpc.net/problem/11068

11068번: 회문인 수

 

 

처음에는 숫자범위인 1,000,000만큼의 배열을 만들어서 풀이하려 했으나 시간초과가 일어나

각 입력받을 때마다 계산을 해주었다. 생각해보니 입력수가 1,000,000번 이하라면 굳이 배열을 다 만들어서 미리 계산해둘 필요가 없을 듯하다.

숫자의 범위가 작을 때 이러한 방법을 써야겠다.

 

 

import java.util.*;
import java.io.*;
public class Main
{

    public static String change(int number, int radix){
        StringBuilder sb = new StringBuilder();
        while(number>0){
            int na = number%radix;
            if(na<10) sb.append(Integer.toString(na));
            else sb.append((char)('A'+na-10));
            number/=radix;
        }
        return sb.reverse().toString();
    }
    public static boolean checkPalindrome(String string){
        StringBuilder sb = new StringBuilder(string);
        if (string.equals(sb.reverse().toString())) return true;
        else return false;
    }
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.valueOf(br.readLine());
	    
	        int num=Integer.valueOf(br.readLine());
            for(int j=2; j<65;j++){
                if (checkPalindrome(change(num,j))){
                    bw.write("1\n");
                    break;
                }else if (j==64){
                    bw.write("0\n");        
                } 
            }
            
        }
        
        bw.flush();
	    
	    
	}
	    
		

	

}

 

 

처음코드(주석처리)

import java.util.*;
import java.io.*;
public class Main
{
    public static boolean[] check = new boolean[1_000_000];
    
    public static void pre(){
        for(int i=0;i<1_000_000;i++){
            for(int j=2; j<65;j++){
                if (checkPalindrome(change(i,j))){
                    check[i]=true;
                    break;
                }
            }
        }
    }
    
    public static String change(int number, int radix){
        StringBuilder sb = new StringBuilder();
        while(number>0){
            int na = number%radix;
            if(na<10) sb.append(Integer.toString(na));
            else sb.append((char)('A'+na-10));
            number/=radix;
        }
        return sb.reverse().toString();
    }
    public static boolean checkPalindrome(String string){
        StringBuilder sb = new StringBuilder(string);
        if (string.equals(sb.reverse().toString())) return true;
        else return false;
    }
    
	public static void main(String[] args) throws IOException {
	   // pre();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.valueOf(br.readLine());
	    
	    for(int i=0;i<n;i++){
	       // bw.write(check[Integer.valueOf(br.readLine())] ? "1\n":"0\n");
	        int num=Integer.valueOf(br.readLine());
            for(int j=2; j<65;j++){
                if (checkPalindrome(change(num,j))){
                    bw.write("1\n");
                    break;
                }else if (j==64){
                    bw.write("0\n");        
                } 
            }
            
        }
        
        bw.flush();
	    
	    
	}
	    
		

	

}

 

모범답안: 회문판단을 위해서는 문자로 변환할 필요가 없다. -> 나머지만 체크하면 된다.

각 자리에 나머지를 저장하고 그 값들을 양쪽에서 비교하는 방식이다.

 

import java.util.Scanner;

class Main
{
    public static boolean isPalindromeInBase(int x, int base) {
        int[] digit = new int[20];
        int len = 0;
        while (x > 0) {
            digit[len++] = x % base;
            x /= base;
        }

        for (int i = 0; i < len / 2; i++)
            if (digit[i] != digit[len - i - 1])
                return false;
        return true;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int x = sc.nextInt();
            boolean ans = false;
            for (int i = 2; i <= 64; i++) {
                if (isPalindromeInBase(x, i)) {
                    ans = true;
                    break;
                }
            }
            System.out.println(ans ? 1 : 0);
        }
    }
}