[1254번] 팰린드롬 만들기 (java)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	9762	4288	3581	45.688%

문제

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

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

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

입력

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

출력

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

예제 입력 1

abab

예제 출력 1

5

예제 입력 2

abacaba

예제 출력 2

7

예제 입력 3

qwerty

예제 출력 3

11

예제 입력 4

abdfhdyrbdbsdfghjkllkjhgfds

예제 출력 4

38

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 문자열
• 브루트포스 알고리즘

나의 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int len = str.length();

        // 1. 문자열 중간에 팰린드롬이 있는지 알아야 함! 
        for (int i = 0; i < str.length(); i++) {
            if (isPalindrome(str.substring(i))) {
                break;
            }
            //3. 팰린드롬 아니면 같은 문자 하나 추가해줘야 하니까 길이 1 추가
            len++;
        }
        System.out.println(len);
    }
    
    private static boolean isPalindrome(String str) {
        int start = 0;
        int end = str.length() - 1;

        // 2. 문자열 맨 앞, 맨 뒤부터 좁혀가면서 팰린드롬인지 확인
        while (start <= end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

몰랐는데, 내가 쓴 방법이 투포인터(Two Pointer) 알고리즘이라고 한다.

다른 사람의 풀이

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

public class Q1254 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        if(isPal(str)) {
            System.out.println(str.length());
            return;
        }

        int cnt = 1;
        while(true){
            str = str.substring(1);

            if(isPal(str)) {
                System.out.println(str.length() + 2 * cnt);
                return;
            }

            cnt++;
        }
    }

    static boolean isPal(String s){
        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i) != s.charAt(s.length()-i-1)) return false;
        }

        return true;
    }
}