[Java] BOJ 1213 팰린드롬 만들기

1213번: 팰린드롬 만들기

---

오답 코드

• 입력 받은 문자열 정렬
• 순열을 활용한 완전 탐색 후 팰린드롬 확인
  • 입력값이 50으로 순열 시간복잡도 O(50!)
  • 시간 초과 발생

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

public class Main {

    static BufferedReader br;
    static char[] arr, copy;
    static int N;
    static boolean flag;
    static String ans;

    public static void main(String[] args) throws NumberFormatException, IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        arr = br.readLine().toCharArray();
        N = arr.length;
        Arrays.sort(arr);
        copy = new char[N];
        Arrays.fill(copy, '0');

        fun(0);

        System.out.println(flag ? ans : "I'm Sorry Hansoo");
    }

    private static void fun(int index) {
        if (flag) {
            return;
        }

        if (index == N) {
            flag = isPalindrome();
            if (flag) {
                ans = new String(copy);
            }
            return;
        }

        for (int i = 0; i < N; i++) {
            if (copy[i] != '0') {
                continue;
            }
            copy[i] = arr[index];
            fun(index + 1);
            copy[i] = '0';
        }
    }

    private static boolean isPalindrome() {
        for (int i = 0; i < N / 2; i++) {
            if (copy[i] != copy[N - i - 1]) {
                return false;
            }
        }
        return true;
    }
}​

 

---

정답 코드

• check 함수로 팰린드롬 생성 여부 확인
  • 알파벳 수 확인하기 
  • 문자열 길이 짝수 : 알파벳 수 모두 짝수인 경우 팰린드롬 생성 가능
  • 문자열 길이 홀수 : 알페벳 수 하나만 홀수인 경우 팰린드롬 생성 가능
• 문제에서 오름차순에서 사전순 첫번째 단어 반환
• 배열 돌면서 해당 문자열 생성

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

public class Main {

    static BufferedReader br;
    static int[] arr;
    static char[] ans;
    static String str;
    static int N;

    public static void main(String[] args) throws NumberFormatException, IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        arr = new int[26];
        N = str.length();
        for (int i = 0; i < N; i++) {
            arr[str.charAt(i) - 'A']++;
        }

        ans = new char[N];
        if (check()) {
            for (int i = 0; i <= N / 2; i++) {
                for (int j = 0; j < 26; j++) {
                    if (arr[j] > 1) {
                        ans[i] = (char) ('A' + j);
                        ans[N - i - 1] = (char) ('A' + j);
                        arr[j] -= 2;
                        break;
                    } else if (i == N / 2 && arr[j] == 1) {
                        ans[i] = (char) ('A' + j);
                        break;
                    }
                }
            }
            System.out.println(new String(ans));
        } else {
            System.out.println("I'm Sorry Hansoo");
        }
    }

    private static boolean check() {
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) {
                cnt++;
            }
        }

        if (cnt == 0) {
            return true;
        } else if (cnt == 1) {
            if (N % 2 == 1) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

}