[자바] 백준 11068 - 회문인 수 (java)

 문제 : boj11068

---

 

필요 알고리즘 개념

• 수학
  
  • 10진수를 2~64진법으로 진법을 변경할 줄 알아야 한다.
• 브루트포스
  • 입력으로 들어온 수에 대해 2~64진법 모두로 변경 후 각각 팰린드롬인지 확인해보면 되므로 브루트포스(완전탐색) 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  난이도가 어려운 문제는 아닌데, 자잘하게 알아야 할게 많은 문제이다.

 

1. 10진수를 2~64진법으로 변경

  10진수를 n진법으로 변경할 경우, 나눈 몫이 0이 될 때 까지 n으로 나눠주고, 그 나눈 나머지를 뒤에서 이어붙이면 해당진법으로 변경이 가능하다.

  예를들어 10진수 10을 2진법으로 바꾸려면..

A. 10을 2로 나누면 몫이5, 나머지 0

B. 5를 2로 나누면 몫이 2, 나머지 1

C. 2를 2로 나누면 몫이 1, 나머지 0

D. 1을 2로 나누면 몫이 0, 나머지 1

 

D부터 역순으로 이어붙이면 1010이 되고 이게 2진법으로 바꾼 결과이다. 마찬가지로 4진법으로 바꾸면 22가 된다.

 

이 때 11진법부터는 한자리 수로 표현이 불가능한데 어떻게 표현할지 궁금할 수 있다. 이 문제에서는 그걸 생각하지 않아도 된다. 어차피 팰린드롬인지만 확인하면 되므로 각 자리수에 어떤값을 가지는지만 알면 된다. '2'를 보면 왜 그런지 알 수 있다.

 

 

2. 팰린드롬 판정

  팰린드롬의 경우 가장 간단하게 판단하는건 맨앞과 맨뒤부터 하나씩 비교해보는 것이다. 이하 풀이에서는 인덱스값을 가지고 비교할 것이지만, 설명을 편히 하기 위해 맨앞을 포인터 st가, 맨뒤를 포인터 ed가 가리키고 있다고 해보자. '1231421'이 팰린드롬인지 판정할꺼다. 그럼 이하 그림처럼 진행되며, '3'과 '4'를 비교할 때 팰린드롬이 아님을 알 수 있게 된다. st<ed 인동안 이하를 진행하고, 모두 통과했다면 팰린드롬이다.

 

  따라서 각 자리수에 해당하는 숫자만 동일하다면 통과시킬 수 있으므로, '1'에서 11진법 이상이더라도 굳이 문자로 변경하지 않아도 비교만 할 수 있으면 되는거다.

  예를들어 10진수 255는 16진법으로 변경 시 FF인데, F는 15에 해당하므로 그냥 15 | 15 처럼 배열이나 ArrayList 형태로 가지고 있으면서 비교만 할 수 있으면 된다.

 

 

3. 정리

  각 테스트케이스마다 입력으로 받은 10진수를 '1'의 방식으로 2~64진법으로 변경한다. 그리고 '2'의 방식으로 각각 팰린드롬인지 판정하다가, 한번이라도 팰린드롬이라면 결과로 1을 출력해주고, 2~64진법 모두 팰린드롬이 아니라면 0을 출력해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    private boolean isPalindrome(int n, int radix) {
        ArrayList<Integer> convert = new ArrayList<>();
        while (n != 0) {
            convert.add(n%radix);
            n/=radix;
        }
        for (int i = 0; i < convert.size()/2; i++) {
            if (convert.get(i) != convert.get(convert.size()-1-i))
                return false;
        }
        return true;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            int num = Integer.parseInt(br.readLine());
            boolean chk = false;
            for (int r = 2; r <= 64 && !chk; r++) {
                chk = isPalindrome(num, r);
            }
            sb.append(chk?1:0).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}