문제 설명

어떤 수를 왼쪽에서 읽어도, 오른쪽에서 읽어도 같다면
이를 회문 수라고 한다.

예를 들어

747

은 회문 수이다.

또한 어떤 수는 다른 진법으로 표현했을 때 회문이 될 수도 있다.

예

255 (10진수) → FF (16진수)

이 경우도 회문이다.

---

목표

주어진 정수 N이

2 ≤ B ≤ 64

범위의 어떤 진법으로 표현했을 때
회문이 되는 경우가 있는지 판단한다.

---

입력

첫째 줄

T

테스트 케이스 개수

각 줄마다 하나의 정수 N

조건

64 ≤ N ≤ 1,000,000

---

출력

각 테스트 케이스마다

• 회문이 되는 진법이 존재하면 1
• 없으면 0

---

입력 예시

3
747
255
946734

출력 예시

1
1
0

---

문제 해결 아이디어

이 문제의 핵심은 두 가지이다.

1. 여러 진법으로 변환
2. 회문인지 검사

---

해결 흐름

1. 주어진 수를 2 ~ 64진법으로 변환
2. 각 진법마다 숫자를 배열에 저장
3. 해당 배열이 앞뒤 대칭인지 검사
4. 하나라도 회문이면 1, 아니면 0

---

내가 작성한 풀이

각 진법마다 직접 변환하고,
배열을 이용해 회문 여부를 검사했다.

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        int[] result = new int[T];

        for (int i = 0; i < T; i++) {

            int N = sc.nextInt();

            for (int base = 2; base <= 64; base++) {

                int[] digit = new int[20];
                int num = N;
                int k = 0;

                while (num > 0) {
                    digit[k] = num % base;
                    num /= base;
                    k++;
                }

                int isPalindrome = 1;

                for (int l = 0; l < k / 2; l++) {
                    if (digit[l] != digit[k - l - 1]) {
                        isPalindrome = 0;
                        break;
                    }
                }

                if (isPalindrome == 1) {
                    result[i] = 1;
                    break;
                }
            }
        }

        for (int i = 0; i < T; i++) {
            System.out.println(result[i]);
        }
    }
}

---

강의 풀이

강의에서는 회문 검사 부분을 함수로 분리하여
코드를 더 깔끔하게 구성했다.

코드

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);
        }
    }
}

---

두 풀이 방식 비교

방식	특징
내 풀이	모든 로직을 main에서 처리
강의 풀이	회문 검사 함수 분리

강의 코드는

함수 분리 → 가독성 향상

이 장점이 있다.

---

핵심 개념

1. 진법 변환

digit = N % base
N = N / base

이 과정을 반복하면 해당 진법의 숫자를 구할 수 있다.

---

2. 회문 검사

배열이

앞에서 읽은 값 = 뒤에서 읽은 값

이면 회문이다.

예

1 2 3 2 1

---

3. 배열은 역순으로 저장된다

진법 변환 과정에서

낮은 자리부터 저장

되므로

digit[0] = 가장 뒤 숫자

형태가 된다.

하지만 회문 검사는 그대로 가능하다.

---

시간 복잡도

각 테스트 케이스마다

• 진법 반복: 63번
• 각 진법 변환: log N
• 회문 검사: O(log N)

따라서 전체 시간 복잡도는

O(T × 64 × log N)

으로 충분히 빠르다.

---

정리

이 문제는 단순히 회문을 검사하는 것이 아니라
여러 진법으로 변환 후 회문 여부를 확인하는 문제였다.

핵심은 다음과 같다.

1. 다양한 진법으로 변환한다.
2. 각 진법에서 회문인지 검사한다.
3. 하나라도 만족하면 바로 종료한다.

강의 코드처럼 회문 검사 로직을 함수로 분리하면
코드를 더 깔끔하게 작성할 수 있다는 점도 배울 수 있었다.