[백준 4096번 / java] 팰린드로미터

문제

4096번: 팰린드로미터 (acmicpc.net)

1. 팰린드로미터 : 거꾸로 읽어도 같은 단어

2. 2<=자리수<=9

풀이

•  팰린드롬인지 확인한다. (투포인터 사용)
  • 맞으면 StringBuilder에 0을 추가
  • 아니면 1씩 더하며 계속 팰린드롬인지 확인하고, 팰린드롬이 되면 지금까지 더한 숫자를 StringBuilder에 추가

try 1

주의할 점은, 아래 코드와 같이 값을 처음부터 int로 받아버리면 '000121'과 같이 앞에 0이 있는 숫자를 121로 인식한다.

따라서 String으로 받아야 한다. 

import java.io.*;
import java.util.*;

public class boj_4096 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sb = new StringBuffer();

        int num = -1;
        while(num != 0){
            num = Integer.parseInt(br.readLine());
            if(isPalindrome(num)){ //팰린드롬이다
                sb.append(0).append("\n");
            }else{
                sb.append(haveToAdd(num)).append("\n");
            }
        }
        bw.write(sb+" ");
        bw.close();

    }
    static boolean isPalindrome(int num){
        int start = 0;
        int end = calc(num)-1;

        int[] arr = new int[end+1];
        for(int i=end; i>=0; i--){
            arr[i] = num%10;
            num /= 10;
        }

        while(start < end){
            if(arr[start] != arr[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
    static int haveToAdd(int num){
        int ret = 0;
        while(!isPalindrome(num)){
            num++;
            ret++;
        }
        return ret;
    }
    static int calc(int num){
        //몇 자리 숫자인지 판별
        int ret = 0;
        while(num>0){
            num/=10;
            ret++;
        }
        return ret;
    }
}

try 2

다음은 String으로 받은 값을 int로 변환한 후, 1씩 더하면서 팰린드롬인지 확인하는 haveToAdd함수이다.

String을 int로 변환해서 1을 더하면 앞서 발생했던 문제와 같은 문제가 또 발생하게 된다.

앞에 0이 붙어있던 것이 무시되고 '000121' -> 121 + 1 -> 122 -> '122'가 된다.

 

그래서 이 문제를 해결하기 위해 해당 자리수의 최솟값 이상이 될 때까지 1을 계속 더하게 만들었다.

그러나 00456에 44만 더하면 00500이 되어 팰린드롬이 만들어질 수 있다. 즉 자리수를 넘지 않아도 된다. 

 static int haveToAdd(String num){
        //num.length()자리수여야 함
        //만약 3자리수면 1000이상이어야 함
        int ret = 0;
        while(true){
            int tmpNum = Integer.parseInt(num);
            if(tmpNum >= Math.pow(10, num.length()-1) && isPalindrome(num))
                break;
            tmpNum++;
            ret++;
            num = Integer.toString(tmpNum);
        }
        return ret;
    }

 

올바른 해결책 :

숫자에 1을 더하고 나서 팰린드롬인지 확인하기 전에 항상 자리수만큼 0을 채워주는 작업을 추가한다.

 

1. 현재 String값을 int로 변환

2. 1을 더함

3. String으로 변환

4. 앞에 원래 자리수만큼 0을 붙여줌

5. 다시 while문의 처음으로 돌아가 팰린드롬인지 확인

코드

import java.io.*;
import java.util.*;

public class boj_4096 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sb = new StringBuffer();


        while(true){
            String num = br.readLine();

            if(num.equals("0"))
                break;

            if(isPalindrome(num)){ //팰린드롬이다
                sb.append(0).append("\n");
            }else{ //팰린드롬이 아니다
                sb.append(haveToAdd(num)).append("\n");
            }
        }

        bw.write(sb+" ");
        bw.close();

    }
    static boolean isPalindrome(String num){
        int start = 0;
        int end = num.length()-1;
        while(start < end){
            if(num.charAt(start) != num.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
    static int haveToAdd(String num){
        int ret = 0; //더해야 할 값
        int length = num.length(); //자리수

        while(!isPalindrome(num)){
            //String을 int로 바꾼 후 +1
            //다시 int를 String으로 바꿔준다
            int next = Integer.parseInt(num) + 1;
            ret++;
            num = Integer.toString(next);

            //자리수 맞추기
            if(num.length() < length){
                String newNum = "";
                for(int i=0; i<length-num.length(); i++){
                    newNum += "0";
                }
                newNum += num;
                num = newNum;
            }
        }
        return ret;
    }
}

Note

• 간단한 문제였지만 시간을 꽉 채워서 풀었다.
• String, int 타입 변환 함수를 검색하며 풀었고, 처음에 앞에 0이 붙어있는 경우를 고려하지 못해서 코드의 모든 부분을 다시 손봐야했기 때문이다.
• 대체 1시간 30분 내에 골드 두 문제, 실버 두 문제를 어떻게 다 푸는 걸까. 나는 아직 실버4문제도 한 시간 반이 걸린다.