[JAVA]BOJ 11068, 회문인 수

 진법변환&Palindrome이 섞인 문제. 각각은 구현해봤지만 섞어서는 처음이다. 앞에 11005번처럼 B진법 문자를 하나하나 다 대응하지 않았다. 출력하지 않으니 굳이 문자를 대응할 필요가 없기 때문이다.

 N이 'B의 ?승 * ?' 의 합으로 표현되는지 계산해 B진법으로 바꿔주었다. 10 -> 2^3*1 + 2^2*0 + 2^1*1 + 2^0*0 이런식으로 표현하는 것이다. 

구하는 방법도 간단하다. for문을 이용해 제일 큰 지수를 구하고, 또 for문을 이용해 B^(제일 큰 지수) * ? 가 N보다 커지는 순간을 찾으면 된다. 그리고 ?를 char배열에 저장한다. char배열은 B진법으로 변환했을때 자릿수 만큼의 크기를 가진다.

 

10 -> 2^3*1 + 2^2*0 + 2^1*1 + 2^0*0 으로 예를 들면,

• 제일 큰 지수는 3
• B진법 변환시 자릿수는 4
• char배열은 4칸이다. -> [0]_ [1]_ [2]_ [3]_
• B^(제일 큰 지수) * ? 에서 ?는 각 1 0 1 0 이 된다.
• ?를 char배열에 [0]1 [1]0 [2]1 [3]0 으로 저장한다.
• char배열이 Palindrome인지 확인한다.

 

 

---

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ11068 {
    public static int checkNtoBPalindrome(int N, int B){
        // 10 -> 2^3*1 + 2^2*0 + 2^1*1 + 2^0*0, 이렇게 만들거고, *? 이 ?를 배열에 저장함, 그 배열을 palindrome 검사
        // N은 int여야 함
        // B진법으로 바꿀때 최대 B^ 지수 먼저 찾기 -> 자릿수 : 최대지수 + 1

        int i, j, max = 1, maxExponent, Nidx;
        char[] NtoBCharArr;
        String str;
        //Nidx 는 B진법 변환시 자릿수 -> 배열 크기 뜻함
        //maxExponent 는 B진법 변환시 최대지수

        // 자릿수와 최대지수 찾기
        for(i=0;N>max;i++){
            max *= B;
        }

        Nidx = i; // 자릿수
        maxExponent = Nidx - 1; // 최대지수
        NtoBCharArr = new char[Nidx]; // B^(maxExponent) * ? -> ? 저장할 배열 크기 맞춰 생성

        for(i=0;i<Nidx;i++){
            max = 1;
            for(j=0;j<maxExponent - i;j++){ // B^(maxExponent) * ? 에서 ?를 구하기 위해 B^(maxExponent)를 계산 -> max에 저장
                max *= B;
            }

            for(j=1;j<B;j++){ // B^(maxExponent) * ? 에서 ?값 찾기
                if(max * j > N)
                    break;
            }
            NtoBCharArr[i] = (char)(j - 1); // ?자리 찾은거 저장
            N -= max * NtoBCharArr[i];
        }

        // 만든 배열을 String으로 바꿔서 palindrome 확인
        str = new String(NtoBCharArr);
        if(CheckPalindrome(str) == 1)
            return 1;
        else
            return 0;
    }


    public static int CheckPalindrome(String N){
        // String N에 대해 Palindrome 확인
        int i, Nidx;

        Nidx = N.length();

        // Palindrome 확인하기
        for(i=0;i<Nidx/2;i++){
            if(N.charAt(i) != N.charAt(Nidx - i - 1))
                break;
        }

        if(i == Nidx/2)
            return 1;
        else
            return 0;
    }

    public static int NtoBPalindrome(int N){
        int i, j;
        String Nstr = N + "";

        if(CheckPalindrome(Nstr) == 1) // 처음에 입력받은 N이 Palindrome 이면 1반환
            return 1;
        else{ // Palindrome이 아니면 진법변환하고 Palindrome 확인
            for(i=2;i<65;i++){
                if(checkNtoBPalindrome(N, i) == 1) // i진법으로 변환한 N이 Palindrome 이면 1반환
                    return 1;
            }
        }
        return 0;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T, i, N;

        T = Integer.parseInt(br.readLine());

        for(i=0;i<T;i++) {
            N = Integer.parseInt(br.readLine());
            System.out.println(NtoBPalindrome(N));
        }
    }
}

 

한 번 글 쓰다가 날라가서 의욕이 줄었다.. 전에 글 되게 꼼꼼히 썼는데 ㅜㅜ.. 그래도 코드에 주석으로 다 설명 달아놨으니까..