백준 | 팰린드롬 만들기

백준 팰린드롬 만들기

팰린드롬(Palindrome) 문자열은 앞에서부터 읽어도, 뒤에서부터 읽어도 동일한 문자열이다. 즉, 완전한 대칭을 이루는 문자열이다.

이 문제는 알파벳 대문자로만 이루어진, 길이 최대 50인 문자열(name)이 주어질 때, 사전 순서를 기준으로 첫 번째에 위치하는 팰린드롬 문자열을 출력하는 것이다.

여기서, name에 포함된 문자 중 그 개수가 홀수인 문자가 2개 이상이라면?
어떤 경우에도 대칭인 문자열이 만들어질 수 없으므로, 팰린드롬 문자열 역시 존재하지 않는다.

그렇지 않고, name에 포함된 문자 중 그 개수가 홀수인 문자가 0개나 1개라면?
팰린드롬 문자열이 만들어질 수 있다.

그리고 어떤 팰린드롬 문자열을 left + mid + right(또는 left[::-1])의 조합으로 생각하면, 사전 순서를 기준으로 첫 번째에 위치하는 left로 만들어지는 팰린드롬 문자열이 문제의 정답이다.

이러한 이유에서 다음과 같이 접근했다.

[1] collectinos.Counter 클래스를 통해 name에 포함된 각 문자의 개수(char_count)를 센다.

[2] char_count의 key(문자), value(문자 개수)를 정렬한다.

[3] name에 포함된 문자 중 그 개수가 홀수인 문자 개수(odd_char)를 센다.

[4-1] odd_char의 길이가 2 이상이면, 팰린드롬 문자열이 만들어질 수 없으므로, I'm Sorry Hansoo를 출력한다.
[4-2] odd_char의 길이가 0 또는 1이면, 그 문자를 팰린드롬의 가운데(mid)에 넣으면 된다.

[5] left에 해당되는 문자열은 사전 순으로 정렬된 char_count를 반복하며, 그 문자와 개수의 절반만큼을 이어 붙이면 된다.

[6] "".join(left) + "".join(odd_char) + "".join(left[::-1])이 문제의 정답이다.

import sys
from collections import Counter

name = sys.stdin.readline().strip()

# 팰린드롬 구하기
char_count = Counter(name)
char_count = sorted(char_count.items())

odd_char = []
for ch, cnt in char_count:
    if cnt % 2 == 1:
        odd_char.append(ch)

if len(odd_char) > 1:
    print("I'm Sorry Hansoo")
else:
    left = []
    for ch, cnt in char_count:
        left.append(ch * (cnt // 2))
    
    print("".join(left) + "".join(odd_char) + "".join(left[::-1]))