[BOJ]1213. 팰린드롬 만들기

문제:

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

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

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

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

입력:

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

출력:

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

풀이방법:

 우선 각 알파벳의 갯수를 count를 한다. 이 때, 홀수 개인 알파벳이 한 개만 있거나 없을 경우에만 팰린드롬을 만들 수 있다. 홀수 개인 알파벳이 하나만 있을때만, 가운데에 배치하여 팰린드롬을 만들 수 있기 때문이다. 따라서 이 조건을 사용해서 우선적으로 필터링해주도록 한다.

 만들 수 있는 경우에는 알파벳을 사전순으로 정렬한 뒤 만들어나가기 시작한다. 각 알파벳의 갯수 M/2개를 문자열에 이어붙이고, 모든 문자열을 순회한 경우에는 다시 역순으로 M/2개를 문자열에 이어 붙이도록 한다. 이 때, 홀수 개인 알파벳이 있었다면, 역순으로 진행하기 전에 먼저 붙이도록 한다.

from collections import Counter
name = input()
c = Counter(name)
counts = sorted(c.most_common())
odd_alpha = list(filter(lambda x: x[1]%2==1, counts))
if len(odd_alpha) > 1:
    print("I'm Sorry Hansoo")
else:  
    answer = ""
    for alpha, count in counts:
        answer += alpha*(count//2)
    if len(odd_alpha):
        answer += odd_alpha[0][0]
    counts.reverse()
    for alpha, count in counts:
        answer += alpha*(count//2)
    print(answer)

문제링크:

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