[백준](2024) 회문인 수 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/11068

 

 

난이도		알고리즘
	실버5	수학, 완전탐색

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 256MB

 

주어진 양의 정수를 어떤 B진법(2 <= B <= 64)으로 표현하면 회문이 되는 경우가 있는지 판단 

 

*  64 <= 주어진 양의 정수 <= 1,000,000 

 

 

 

 

2. 설계/검증 

입력

- T : 테스트 케이스 개수

- 정수 

 

설계

- 2~64까지 진법 변환

- 회문 판별 

 

 

출력 
- 각 줄에 각 테스트 데이터가 회문이 될 수 있으면 1, 아니면 0

시간 복잡도	최악의 경우	공간 복잡도
O(T * logN)	O(T)	O(1)

 

 

 

3. 정상 코드

import java.util.*;

public class main {

    public static void main(String[] args) {
        // Scanner 객체 생성
        Scanner scan = new Scanner(System.in);

        //테스트 케이스의 개수 입력
        int T = scan.nextInt();

        //각 테스트 케이스에 대한 처리
        for (int i = 0; i < T; i++) {
            //주어진 수 입력
            long num = scan.nextLong();

            // 어떤 B진법으로 표현하여 회문이 될 수 있는지 찾아서 결과 출력
            int result = findPalindromeBase(num);
            System.out.println(result);
        }

        scan.close();
    }

    // 어떤 진법으로 표현하여 회문이 될 수 있는지를 판단하는 메소드
    private static int findPalindromeBase(long num) {
        // 2진법부터 64진법까지 확인
        for (int B = 2; B <= 64; B++) {
            // 주어진 수를 B진법으로 표현한 문자열 얻기
            String numStr = Long.toString(num, B);

            if (isPalindrom(numStr)) {
                return 1; // 회문인 경우
            }
        }
        return 0; // 회문이 아닌 경우
    }

    // 문자열이 회문인지를 판단하는 메소드
    public static boolean isPalindrom(String str) {

        // 문자열 양 끝에서부터 비교하며 회문 여부 확인
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false; // 회문이 아닌 경우
            }
            left++;
            right--;
        }

        return true; // 회문인 경우
    }
}

 

 

추가 정리

회문

= 팰린드롬(palindrome)

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다.

 

 

Long.toString(long i, int radix)

Java의  Long클래스에 속한 toString 매서드의 일부분으로 

long 값을 특정 진수radix로 표현하는 문자열을 반환합니다.

 

• 문자열의 구성
  • 나머지 문자들은 입력값의 절대값을 주어진 진수로 변환하여 나타냅니다.
  • 변환에 사용되는 문자는 주어진 진수에 따라 0부터 9까지 숫자 및 a부터 z까지 알파벳입니다. 
  • 결과 문자열의 첫 문자는 0이 아닌 경우에만 포함됩니다.
• 음수처리 
  • 만약 입력 값 i 가 음수인 경우, 결과 문자열의 첫 문자로 ascii 마이너스 부호('-')가 추가됩니다.
• 진수처리
  • 만약 주어진 진수가 유효한 범위를 벗어난 경우 Character.MIN_RADIX,
  • 큰 경우 Character.MAX_RADIX,
  • 기본적으로 10진수 처리됩니다.
  • 만약 진수가 10진수인 경우, toString(i) 메서드를 호출하여 해당 값을 10진수로 반환합니다.