(22.06.26) (Baekjoon) 1213.팰린드롬 만들기

1213번: 팰린드롬 만들기

시간 제한 : 2초

메모리 제한 : 128MB

사용 알고리즘 : 구현, 문자열,그리디 알고리즘

 

문제

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

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

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

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

입력

 

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

출력

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

예제 입력 1 복사

AABB

예제 출력 1 복사

ABBA

예제 입력 2 복사

AAABB

예제 출력 2 복사

ABABA

예제 입력 3 복사

ABACABA

예제 출력 3 복사

AABCBAA

예제 입력 4 복사

ABCD

예제 출력 4 복사

I'm Sorry Hansoo

 

말 그대로 팰린드롬을 만드는 문제다.

(※ 팰린드롬 : 앞~중간 == 뒤~중간으로 읽히는 문자열이 같은 문자 (ex. ABCBA ==> 앞~중간 : ABC // 뒤 ~중간 : ABC))

팰린드롬을 만들 수 있다면 만들어진 팰린드롬을 출력하고(여러개가 나올 경우 사전 순으로 가장 빠른 팰린드롬)

만들 수 없다면 " I'm Sorry Hansoo "를 출력하면 된다.

 

일단 하나씩 접근해보자.

1) 팰린드롬 만드는 법

1- 주어진 문자열을 오름차순으로 정렬한다.(ex ABABA => AAABB)

2- for문을 돌려, 1-5-2-4-3과 같은 순서로 문자를 추가해준다.

(AAABB => AABB (A        ) => ABB(A      A) => BB(A  A  A) => B(ABA  A) => ""(ABABA)

이 방식이면 늦은 문자가 뒤에 오기 때문에 사전 순으로 가장 빠른 팰린드롬이 완성될 수 있다.

 

2) 팰린드롬의 생성 가능 여부

전체 문자열의 길이와, 그에 따른 홀수개를 가지는 문자의 개수를 가지고 확인할 수 있다.

 

1-1) 문자열의 길이가 짝수일 경우(AB, ABAB, AAABBB)

이땐 AAA같이 홀수개를 가지는 문자열이 존재해선 안된다.

 

1-2) 문자열의 길이가 홀수일 경우(A, ABA, ABCAB,AABBBCCC)

홀수개를 가지는 문자열이 1개까진 허용된다.

즉, AABBBCCC 같은 BBB,CCC를 가지는 문자열은 팰린드롬으로 만들 수 없다.

 

이제 조건을 다 찾았으면 위 조건을 유의하면서 팰린드롬을 만들어보면 된다.

 

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

public class Main {
	static int[] alp = new int[26];
	static String wrong = "I'm Sorry Hansoo";
	static char[] str, ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine().toCharArray();
		ans = new char[str.length];
		Arrays.sort(str);
		int len = str.length;
		int even = 0; 
		int odd = 0;
		for (int i = 0; i < str.length; i++) {
			alp[str[i]-'A']++;
		}
		for (int i = 0; i < 26; i++) {
			if(alp[i] > 0) {
				if(alp[i] % 2 == 0) even++;
				else odd++;
			}
		}
		if(len %2 == 0) { 
			if(odd > 0) { 
				System.out.println(wrong);
				return;
			}
		}
		else { 
			if(odd > 1) { 
				System.out.println(wrong);
				return;
			}
			for (int i = 0; i < 26; i++) {
				if(alp[i] %2 != 0) {
					char temp = '.';
					 for (int j = 0; j < str.length; j++) {
						if(str[j]-'A' == i && temp == '.') {
							temp = str[j];
							continue;
						}
						if(temp != '.') {
							str[j-1] = str[j];
						}
					}
					str[str.length-1] = temp;
					break;
				}
			}
		}
		int idx = 0;
		for (int i = 0; i < str.length; i++) {
			if(i %2 == 0) {
				ans[idx] = str[i];
			}
			else {
				ans[str.length-1-idx] = str[i];
			}
			if(i != 0 && i % 2 != 0) {
				idx++;
			}
		}
		System.out.println(ans);
	}
}