[Baekjoon] 1213번: 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

문제 설명

주어진 문자열로 팰린드롬을 만들어서 출력하면 된다. 팰린드롬이 불가능하다면 I'm Sorry Hansoo 를 출력하면 된다.

팰린드롬은 ABCBA와 같이 앞으로 봐도 뒤집어 봐도 똑같은 문자열을 말한다.

풀이 방법

문자열의 등장 횟수를 배열에 저장하는 방법으로 해결할 수 있다.

예를 들어 ABACABA 라는 문자열이 입력되었다고 하자. 이 경우 A = 4, B = 2, C = 1 인 것을 알 수 있다.

 

1. 먼저 배열을 사전 순으로 순회하면서 ( 문자열의 등장 횟수 / 2 ) 만큼 문자열을 추가한다. 위 예라면 AAB 가 될 것이다. C는 1이기 때문에 1 / 2 = 0이 되므로 추가되지 않는다. 이때 AAB는 따로 저장해둔다.
2. 등장 횟수가 홀수인 문자를 찾아 문자열에 추가한다. 따라서 C가 추가되어 AABC가 된다.
3. 이 문자열을 뒤집어서 앞에서 저장해 둔 AAB에 추가하면 AABCBAA 가 된다.

팰린드롬이 불가능한 경우는 서로 다른 문자 등장 횟수가 홀수인 경우가 2번 이상인 경우다. 대칭이 되려면 모든 문자 등장 횟수가 짝수이거나 하나의 문자만 홀수여야 한다.

가능한 경우

ABA(홀수개 하나), AABB(짝수개), ABBCA(홀수개 하나), ABCCBA(짝수개)

불가능한 경우

AAABBB(홀수개 둘), ABC(홀수개 셋), ABBC(홀수개 둘)

 

코드는 다음과 같다.

package baekjoon.string;

import java.io.*;

public class BOJ1213 {

    static int[] alphabets = new int[26];

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            char[] name = br.readLine().toCharArray();

            for (char alphabet : name) {
                alphabets[alphabet - 'A']++;
            }

            // 홀수 개인 알파벳이 2개 이상이면 불가능
            int isOnlyOne = 0;
            for (int i = 0; i < alphabets.length; i++) {
                if (alphabets[i] % 2 != 0)
                    isOnlyOne++;
            }

            String answer = "";
            StringBuilder sb = new StringBuilder();

            if (isOnlyOne > 1)
                answer = "I'm Sorry Hansoo";
            else {
                for (int i = 0; i < alphabets.length; i++) {
                    for (int j = 0; j < alphabets[i] / 2; j++) {
                        sb.append((char) (i + 65));
                    }
                }

                answer += sb.toString();

                for (int i = 0; i < alphabets.length; i++) {
                    if (alphabets[i] % 2 == 1)
                        sb.append((char) (i + 65));
                }

                answer += sb.reverse().toString();
            }

            System.out.println(answer);
        }
    }
}