[Java] 백준 1213번 : 팰린드롬 만들기

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

예제 입력 1

AABB

예제 출력 1

ABBA

예제 입력 2

AAABB

예제 출력 2

ABABA

예제 입력 3

ABACABA

예제 출력 3

AABCBAA

예제 입력 4

ABCD

예제 출력 4

I'm Sorry Hansoo

 

소스코드

import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	private static Map<String, Integer> m=new TreeMap<>();	// 정답이 여러 개일 경우 사전순으로 앞서는 것을 출력해야 하므로, HashMap이 아니라 TreeMap을 사용
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s=null;
		
		s=sc.next();
		char ch[]=new char[s.length()];
		for(int i=0;i<s.length();i++) {
			ch[i]=s.charAt(i);
		}
		Arrays.sort(ch);	// 정답이 여러 개일 경우 사전순으로 앞서는 것을 출력하기 위해 배열을 정렬함
		
		for(int i=0;i<s.length();i++) {	// Map에 문자열에 등장하는 알파벳의 개수를 저장함
			String key=ch[i]+"";
			if(m.containsKey(key)) {
				m.put(key, m.get(key)+1);
			} else {
				m.putIfAbsent(key, 1);
			}
		}
		
		
		int cnt=0;
		boolean isImpossible=false;	// 팰린드롬이 불가능한 경우를 확인
		String resultPre="";
		String resultMid="";
		String resultPost="";
		String result=null;
		
		for(Map.Entry<String, Integer> entry:m.entrySet()) {
			String key=entry.getKey();
			Integer value=entry.getValue();
			
            // 홀수가 2개 이상 나오면 팰린드롬 불가능
			if(value%2==1) {
				cnt++;
				resultMid=key;
			}
			if(cnt>1) {
				isImpossible=true;
				break;
			} else {	// 팰린드롬이 가능한 경우, 문자열 가운데 부분에 해당 문자열을 두 개씩 추가해줌. 해당 과정을 알파벳 개수/2 만큼 반복
				int len=value/2;
				for(int i=0;i<len;i++) {
					result=resultPre+key+key+resultPost;
					resultPre=resultPre+key;
					resultPost=key+resultPost;
				}
			}
		}
		if(!isImpossible) {	// 홀수인 문자열을 최종적으로 추가해줌
			result=resultPre+resultMid+resultPost;
		} else {
			result="I'm Sorry Hansoo";
		}
		System.out.println(result);
	}
}

1. 알파벳 개수가 홀수인 경우를 확인합니다.

    1-1. 홀수인 경우가 2번 이상이면 팰린드롬이 불가능합니다.

    1-2. 홀수인 경우가 1번 이하이면 팰린드롬이 가능합니다.

 

2. 1-2.인 경우, 알파벳 개수가 짝수인 경우를 먼저 적용합니다.

    2-1. result 문자열 가운데에 해당 알파벳을 2개씩 추가합니다.

    2-2. 2-1.을 알파벳 개수/2 만큼 반복합니다.