[백준 01213] 팰린드롬 만들기 [Python]

문제

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

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

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

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

입력

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

출력

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

1213번: 팰린드롬 만들기

---

풀이

입력받은 문자열로 팰림드롬 문자열을 만들 수 있는지 확인하고, 만드는 문제다.

우선 입력받은 문자열의 각 문자 갯수를 세주자.

 

만약 문자열의 길이가 짝수라면 홀수개의 문자는 없어야하고,

문자열의 길이가 홀수라면, 홀수개의 문자는 1개만 있어야 한다.

사전순으로 정렬된 팰린드롬 문자열을 만들어야 하므로 A부터 시작해 2개 이상 존재하는 문자를 찾아주자.

 찾았다면, 양쪽 끝에 문자를 넣어주고 문자 갯수를 감소시키자.

만약, 보유 갯수가 1개 이하인 경우에는 다음 문자로 넘어가거나, 나중에 중앙에 삽입해야 한다.

alpha를 다시 탐색하기보다는 odd_count를 통해 남은 문자를 중앙에 삽입해 팰린드롬 문자열을 완성하자