백준1254번) 팰린드롬 만들기

https://www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

◇ 문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

◇ 입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

◇ 출력

 

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

---

◆ 풀이

우선 이미 팰린드롬인 상태를 생각해보자.

abcba

S[0]가 S[S.length-1]와 동일한 character인지 확인. => true

S[1]가 S[S.length-2]와 동일한 character인지 확인. => true

코드로는 다음과 같이 작성할 수 있을 것이다.

boolean result = true;

char[] arr = S.toCharArray();
for(int i=0, iMax = arr.length/2; i<iMax; i++){
	if(arr[i] != arr[S.length()-i-1]){
    	result = false;
        break;
    }
}

return result ? 0 : TODO;

만약 팰린드롬이 되기에 한 글자가 부족한 상황이라면 어떨까?

abcb

우선 S[0]과 S[S.length-1]은 동일하지 않다. 그렇기 때문에 우선 부족한 글자를 저장한다.

그리고 S[1]과 S[S.length-1]을 확인 => true.

코드로 나타내면 다음과 같다.

Stack<Character> stack = new Stack<>();

char[] arr = S.toCharArray();
for(int i=0, iMax = arr.length/2; i<iMax; i++){
    if(arr[i] != arr[S.length()-i+stack.size()-1]){
        stack.push(arr[i]);
    }
}

return S.length() + stack.size();

그리고 이번에는 모든 단어가 서로 다른 케이스다.

qwerty

이 경우에는 q부터 t까지 탐색해야한다.

때문에 조건을 약간 수정해야함을 알 수 있다.

Stack<Character> stack = new Stack<>();

char[] arr = S.toCharArray();
for(int i=0; i<arr.length && stack.size() < arr.length ; i++){
    if(arr[i] != arr[S.length()-i+stack.size()-1]){
        stack.push(arr[i]);
    }
}

return S.length() + stack.size();

이것을 기반으로 제출해보았다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result = palindrome(br.readLine());
        System.out.println(result);
    }

    public static int palindrome(String S){
        Stack<Character> stack = new Stack<>();

        char[] arr = S.toCharArray();
        for(int i=0; i<arr.length && stack.size() < arr.length ; i++){
            if(arr[i] != arr[S.length()-i+stack.size()-1]){
                stack.push(arr[i]);
            }
        }

        return S.length() + stack.size();
    }
}

그러나 틀렸다.

내가 생각하지 못한 예외상황이 무엇이 있나 고민해보았다.

왠지 연속되는 문자가 나오는 경우에는 문제가 될 수 있을 것 같다는 생각이 들었다.

abbccbbba

기존의 코드대로라면 stack의 값을 c와 b 사이에 insert 한다는 가정 하의 길이다.

그래서 코드를 다음과 같이 수정해보았다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result = palindrome(br.readLine());
        System.out.println(result);
    }

    public static int palindrome(String S){
        int count =0;

        char[] arr = S.toCharArray();
        for(int i=0; i<arr.length && count < arr.length ; i++){
            int backIndex = S.length()-i+count-1;
            if(arr[i] != arr[backIndex]){
                count = i;
            }
        }
        count+=S.length();
        return count;
    }
}

일단 생각해보면 Stack이 있어야할 이유가 없어서 우선 int로 변환하였다.

그리고 count를 굳이 계산할 필요가 없었다.

중간에 다른 문자가 나온다는 말은 펠린드롬이 아니라 그만큼 덮어쓰기 하는 것이기 때문이다.

그리고 틀렸다.

그래서 이번엔 그냥 아예 매번 팰린드롬인지 체크하게 만들어보았다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result = palindrome(br.readLine());
        System.out.println(result);
    }

    public static int palindrome(String S){
        int count =S.length();

        for(int i=0, iMax = S.length(); i<iMax; i++){
            if(!isPalindrome(S.substring(i))){
                count++;
            }
            else
                break;
        }
        return count;
    }

    private static boolean isPalindrome(String S){
        boolean result = true;

        char[] arr = S.toCharArray();
        for(int i=0, iMax = arr.length/2; i<iMax; i++){
            if(arr[i] != arr[S.length()-i-1]){
                result = false;
                break;
            }
        }

        return result;
    }
}

드디어 맞았다.

앞으로는 예외 케이스가 따로 떠오르는 게 없으면 확실한 방법을 택해야겠다.