백준 1213 팰린드롬 만들기(구현)

꽤나 푸는데 오래걸린 문제이다.. 2주전부터 거의 3~4번 도전한 것 같은데 구현 실력이 부족해서인지 오래걸린 것 같다.

우선 생각하는 방법은 맞았다.
주어진 문자열의 길이가 짝수라면 글자가 짝수개 씩 있어야한다. 예를 들어, AABBCD라면 A가 2개, B가 2개, C가 1개, D가 1개이므로 안된다. 대칭을 이뤄야하기 때문에 홀수개는 될 수 없다.

주어진 문자열의 길이가 홀수라면 한개의 문자가 홀수개인 것 까지만 허용이 된다. 예를 들어, ABCAB라면 A가 2개, B가 2개, C가 1개이므로 팰린드롬을 만들 수 있다. 하지만, ABCAACC 라면 불가능하다.

또한 중요한 부분은 정답이 여러개라면 사전순으로 앞에 있는 것을 출력하는 것이다. 예를들어, ABAABA가 있다면 답은 AABBAA가 되어야 한다. 따라서 아스키 코드값이 앞인 문자들을 먼저 처리해야 한다는 것이다. 이 말은 밑의 코드와 같다.

for(int i=0; i<alpha.length; i++){      //사전 순으로 앞서려면 아스키 코드가 빠른 순서부터 우선적으로 처리
                for(int j=0; j<alpha[i]/2; j++){
                    output += (char)(i + 'A');
                }
            }

전체 코드는

import java.util.*;

public class Main {
    static String output = "";
    static String s;
    static String add_String(String k){
        String n = "";
        for(int i=k.length()-1; i>=0; i--){
            n += k.charAt(i);
        }
        return n;
    }

    public static void main (String[]args){
        Scanner scanner = new Scanner(System.in);
        s = scanner.next();  //홀수개 글자면 하나만 홀수 나머지 짝수.. 짝수개 글자면 모든게 짝수..
        int[] alpha = new int[26];

        for(int i=0; i<s.length(); i++){
            alpha[s.charAt(i) - 'A']++;
        }
        int center = 0;
        int cnt = 0;
        for(int i=0; i<alpha.length; i++){
            if(alpha[i] % 2 != 0){
                cnt++;
                center = i;
            }
        }
        if(cnt >= 2 || (s.length() % 2 == 0 && cnt >= 1))
            System.out.print("I'm Sorry Hansoo");
        else {
            for(int i=0; i<alpha.length; i++){      //사전 순으로 앞서려면 아스키 코드가 빠른 순서부터 우선적으로 처리
                for(int j=0; j<alpha[i]/2; j++){
                    output += (char)(i + 'A');
                }
            }
            if(s.length() % 2 != 0){
                String k = output;
                output += (char)(center + 'A') + add_String(k);
                System.out.print(output);
            }
            else {
                System.out.print(output + add_String(output));
            }

        }
    }
}

이며, 홀수개의 글자일 때 중간 글자를 더한 뒤 reverse 해줘야한다.