[BaekJoon] #1213 펠린드롬 만들기

문제이해

이 문제는 입력받은 임의의 String을 펠린드롬으로 만들 수 있다면, 펠린드롬으로 만들어 출력하고, 만들 수 없다면, "I'm Sorry Hansoo" 를 출력하는 문제입니다.

문제접근

문제풀이

펠린드롬 핵심

펠린드롬은 순서를 거꾸로 읽었을때도 원래의 문자열이나 수열과 동일한 경우를 말 합니다.

펠린드롬의 조건은 다음 두가지와 같습니다.

1. 모든 문자의 개수가 짝수여야 펠린드롬이 될 수 있습니다.
2. 이때, 최대 하나의 문자는 홀수개여도 됩니다. 만약 홀수인 문자가 문자가 두개 이상 나온다면 펠린드롬을 만들 수 없으므로, 최대 하나의 문자가 홀수개이고 나머지 문자는 모두 짝수개이여야 합니다.

즉, 홀수인 문자가 두개 이상 나오면 펠린드롬을 만들 수 없습니다.

문제풀이 핵심

• 홀수인 문자가 두개 이상 나오면 펠린드롬을 만들 수 없습니다.
• 문자에 대한 빈도수를 효율적으로 세기 위해 문자를 인덱스로 변환해줍니다. 이 과정중에 문자열 정렬도 포함됩니다.
• reverse() 를 사용하면 좌우대칭인 문자를 쉽게 출력할 수 있습니다.

문자를 인덱스로 변환

다음과 같이 문자를 꺼내 'A' 를 빼준다면 알파벳을 0부터 25까지의 인덱스에 대응시킬 수 있습니다.

이후 arr 배열에 각 문자에 해당하는 인덱스에 카운트값을 세줍니다.

arr의 각 인덱스는 A부터 Z까지 순서대로 매핑되어있으므로, 정렬됨과 동시에, arr 배열 안에는 각 문자에 대한 개수를 담게됩니다.

arr을 순회하며 각각의 알파벳 빈도를 체크합니다.

홀수개의 문자 처리

펠린드롬 가능한 경우 출력부분

각 알파벳의 절반을 StringBuilder에 append해주고, 홀수개의 문자가 있다면 또다시 append해주면 됩니다.

나머지 절반도 StringBuilder 객체를 reverse()메소드를 이용해 반전시켜준 이후에, 문자열로변환시켜 결과문자열에 append해주면 됩니다.

code

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


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

        int[] arr = new int[26];
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<s.length(); i++){
            int index = s.charAt(i)- 'A';
            arr[index]++;
        }

        int odd =0;
        int num = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 != 0) {
                odd++;
                num = i;
            }
            if (odd >= 2) {
                System.out.println("I'm Sorry Hansoo");
                return;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i] / 2; j++) {
                sb.append((char)(i+'A'));
            }
        }
            String result = sb.toString();
            if (odd == 1) {
                result += (char) (num + 'A');
            }

            result += sb.reverse().toString();
            System.out.println(result);

        }
    }