[자바] 백준 4096 - 팰린드로미터 (java)

 문제 : boj4096

---

 

필요 알고리즘 개념

• 브루트포스
  
  • 모든 경우의 수를 확인해보는 브루트포스 알고리즘으로 풀 수 있는 문제이다.

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

 

---

 

풀이

 

팰린드롬 판정 방법

  우선 팰린드롬인지 판정하는 방법부터 알아보자. "1231321"를 가지고 생각해보자.

1. 우선 길이를 가지고 반반으로 나눈다. 이 때 홀수라면 정중앙은 무시하면 된다.

2. 그리고 반반으로 나뉜 부분중 아무거나 하나를 돌린다. (123 -> 321)

3. 그렇게 둘이 동일한지 확인하면 된다.

 

 

  이걸 좀 더 코드적으로 편한 방법으로 생각해보면, 결국 가장 좌측과 가장 우측에서 포인터가 하나씩 있다고 생각하고 중앙으로 모이면서 한 문자씩 서로 비교해주면 된다. 포인터가 서로 반대방향으로 움직이므로 한쪽을 거꾸로 돌린 것과 마찬가지이다. "1231421"을 보면, 처음엔 1==1이고, 다음은 2==2이고, 그 다음은 3!=4이므로 팰린드롬이 아님을 알 수 있다.

---

 

풀이1 - String으로 팰린드롬 판정하기

  그럼 다시 문제로 돌아와서, 결론부터 말하자면 그냥 수를 1씩 증가시키면서 팰린드롬이 될때까지 만들어보면 되는 문제이다. 최대 9자리이므로 뭔가 O(10^9)수준이 나올 것 같이 생겼지만, 사실 팰린드롬이므로 절반씩만 동일하면 되서, 왠만하면 1만번 이하로 모두 끝난다. 예를들어 "000000001" 이거 상당히 오래걸릴 것 같지만 1만번 이내로 끝난다. "123450001" 요것도 1만번 이하로 끝난다.

 

  이 문제에서는 각 테스트케이스에서 입력된 문자열의 자리수가 중요하다. 왜냐하면 문제의 조건에 따라 자리수를 줄일 수는 없고, 어차피 99999가 되면 팰린드롬이 될 수 밖에 없으므로 해당 자리수와 동일한 팰린드롬은 무조건 발생한다.

따라서

1. 처음 입력된 자리수를 알고 있어야 한다.

2. 이후 입력된 숫자부터 1씩 증가하면서 팰린드롬 판정을 해줘야 한다.

 

  그렇다면 그냥 매번 수를 1씩 증가시키고, 해당 수를 String으로 바꿔보자. 그리고 그 앞에 '처음 입력된 자리수 - 현재 수를 String으로 바꾼 길이' 만큼 '0'을 붙여주면 된다. 예를들어 처음 입력이 "00023"이라면 len=5가 된다. 23을 +1해주면 24가 되고, 그걸 String으로 바꾸면 길이가 2가 되므로 앞에 0을 3번 붙여주면 "00024"를 만들 수 있다. 그리고 위에서 얘기한 팰린드롬 판정 방식을 적용해주면 String에 대한 팰린드롬 판정을 할 수 있다. 코드의 isPalindrome() 을 참고해보자.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private boolean isPalindrome(int len, int num) {
        String tmp = String.valueOf(num);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len-tmp.length(); i++) {
            sb.append('0');
        }
        sb.append(tmp);
        tmp = sb.toString();

        int st = 0, ed = len-1;
        for (int i = 0; i < len/2; i++) {
            if (tmp.charAt(st+i) != tmp.charAt(ed-i))
                return false;
        }
        return true;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            String s = br.readLine();
            if (s.length()<2) break;
            int len = s.length();
            int num = Integer.parseInt(s);
            int cnt = 0;
            while (!isPalindrome(len, num+cnt++)) {}
            sb.append(cnt-1).append('\n');
        }
        System.out.print(sb);
    }

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

 

---

 

풀이2 - 더 효율적으로 하고싶싶다면, 그냥 int만 가지고 팰린드롬을 판정해보자.

위가 풀이1, 아래가 풀이2 이다. 메모리, 시간 모두 효율성 차이가 크다.

  당연히 String을 만들지 않는게 시간복잡도, 메모리 복잡도 모두 효율적일 것임은 알 수 있을 것이다. 하지만 자리수를 맞춰줘야 하는데 이걸 int로 어떻게 처리할 수 있을까? 예를들어 "00000001"은 int로 표현하면 1일 뿐이다. 또 그럼 위에서 얘기한 팰린드롬 판정 방식은 어떻게 적용시킬 수 있을까?

 

  나누기 '/'와 나머지 연산 '%'을 잘 활용해주면 된다. 코드를 참고하라고 하기도 뭐하고 설명하기도 뭐하니 예시를 들어서 로직 순서대로 확인해보자. "00004" 를 생각해보자.

1. 입력값의 자리수 len은 5이다.

2. 입력값을 수로 바꾸면 4이다.

3. len을 기준으로 baseHigh를 설정할꺼다. 10^(len-1)로 설정할꺼니까 10000이 된다. baseLow는 10으로 할꺼다.

 

  이렇게 두면 int인 4만 있어도 팰린드롬인지 판단 가능하다!

4. low = baseLow, high = baseHigh이다.

5. num은 현재 4이다.

6. (num%low)/(low/10)은 len을 기준으로 수를 늘렸을 시, 즉 int지만 00004라고 봤을 때 가장 왼쪽의 수이다. 풀이 1의 st와 동일하다.

7. (num/high)%10은 가장 오른쪽 수이다. 풀이 1의 ed와 동일하다.

8. 이후 low는 10을 곱해주고(포인터를 좌측으로 하는것과 동일), high는 10을 나눠준다 (포인터를 우측으로 하는 것과 동일)

9. 6~7을 6과 7에서 나온 결과가 다를때까지 모두 통과한다면 팰린드롬이다.

10. 아무래도 설명이 망한 것 같다.. 어떻게 설명해야할지 잘 모르겠다. 음.. isPalindrome 함수의 코드를 직접 손으로 그려보면서 해보면 이해될 것이다!!

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    int len, baseLow, baseHigh;

    private boolean isPalindrome(int num) {
        int low = baseLow;
        int high = baseHigh;
        for (int i = 0; i < len/2; i++, low*=10, high/=10)
            if ((num%low)/(low/10) != (num/high)%10) return false;
        return true;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String s = br.readLine();
        do {
            len = s.length();
            baseLow = 10;
            baseHigh = 1;
            for (int i = 0; i < len-1; i++) baseHigh*=10;
            int num = Integer.parseInt(s);
            int cnt = -1;
            while (!isPalindrome(++cnt+num)) {}
            sb.append(cnt).append('\n');
            s = br.readLine();
        } while (s.length()>1);
        System.out.print(sb);
    }

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