팰린드롬

팰린드롬이란?

앞에서부터 읽어도, 뒤에서부터 읽어도 동일한 문자열이다.

예로 들면 ab는 팰린드롬이고, abb는 팰린드롬이 아니고 aba는 팰린드롬이다.

 

쉬운 문제로 가끔 문제로 출제될 수도 있는데, 알고 있으면 쉽게 풀 수 있기에 공유해 보고자 한다.

기본적인 팰린드롬을 판별하는 방법은 for문을 활용해서 뒤에서부터 앞에까지 읽어왔을 때에 동일하다면 팰린드롬으로 보면 된다.

팰린드롬 문제에서는 기본적으로는 팰린드롬을 구현하기 때문에 메서드로 만들어 놓고 문제를 풀어보면 좋을듯하다. 

 

하단에 팰린드롬을 학습할 수 있는 문제들을 단계별로 모아보았다.

만약 풀이가 궁금해서 들어오신 분들은 바로 해당 문제의 접근 방법과 풀이를 확인해 보면 될 것 같다.

 

팰린드롬인지 확인하기(브론즈2)

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

10988번: 팰린드롬인지 확인하기

[풀이]

- 가장 앞에 문자와 뒤에 문자를 비교 진행

- 모두 비교할 필요가 없으므로 s.length()/2를 해서 반만 비교

package Baekjoon;
import java.util.Scanner;

public class BOK_10988 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(palindrome(sc.next()));
    }

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

팰린드롬(실버5)

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

8892번: 팰린드롬

[풀이]

- A문자와 B문자를 AB, BA 이런식으로 앞뒤로 붙여가면서 Palindrome인지 비교

- Palindrome을 비교하는 부분은 따로 메소드로 분리해주었음.

- 문자열 추가 시 약간의 성능을 기대하고자 StringBuffer 사용

package Baekjoon;

import java.util.ArrayList;
import java.util.Scanner;

public class BOK_8892 {
    public static void main(String[] args) {
        solution();
    }
    static void solution(){
        Scanner sc = new Scanner(System.in);
        ArrayList<ArrayList> totalArray = new ArrayList<>();
        int T = sc.nextInt();
        int k;
        for(int i=0; i<T; i++){
            k = sc.nextInt();
            ArrayList<String> array = new ArrayList<>();
            for(int j=0; j<k; j++){
                array.add(sc.next());
            }
            totalArray.add(array);
        }
        

        for(int i=0; i<totalArray.size(); i++){
            boolean isPalindrome = false;
            for(int j=0; j<totalArray.get(i).size()-1; j++){
                for(int z=j+1; z<totalArray.get(i).size(); z++){
                    StringBuffer sb = new StringBuffer();
                    sb.append(totalArray.get(i).get(j));
                    sb.append(totalArray.get(i).get(z));
                    if(palindrome(String.valueOf(sb))){
                        System.out.println(String.valueOf(sb));
                        isPalindrome = true;
                        break;
                    }
                    sb = new StringBuffer();
                    sb.append(totalArray.get(i).get(z));
                    sb.append(totalArray.get(i).get(j));
                    if(palindrome(String.valueOf(sb))){
                        System.out.println(String.valueOf(sb));
                        isPalindrome = true;
                        break;
                    }
                }
                if(isPalindrome) {
                    break;
                }
            }
            if(!isPalindrome){
                System.out.println("0");
            }
        }
    }
    static boolean palindrome(String s){
        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i) != s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}

팰린드롬 만들기(실버2)

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

1254번: 팰린드롬 만들기

[풀이]

- 만약 입력한 문자가 팰린드롬이면 바로 문자의 크기를 출력

- 앞에서부터 문자를 지워나가면서 팰린드롬인지 확인 (palindrome(s.substring(i, s.length())) 후, 팰린드롬이 되면 지워진 숫자만큼 더해주어 출력 s.length()+i

package Baekjoon;
import java.util.Scanner;

// 팰린드롬 만들
public class BOK_1254 {
    public static void main(String[] args) {
        System.out.println(solution());
    }
    static int solution(){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        if(palindrome(s)){
            return s.length();
        }

        for(int i=1; i<s.length(); i++) {
            if(palindrome(s.substring(i, s.length()))){
                return s.length()+i;
            }
        }
        return 0;
    }
    static boolean palindrome(String s){
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) != s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}