[🥈4 / 백준 1213 / 파이썬] 팰린드롬 만들기

 

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

 

풀이

 

주어진 문자열의 순서를 바꿔 팰린드롬을 구성하는 문제이다.

 

 

필자는 팰린드롬을 왼쪽, 가운데, 오른쪽 3 가지 부분으로 나누어 생각했다.

따라서 왼쪽만 구성한 다음, 만약 가운데에 올 문자열이 있으면 놓아준다.

그리고 왼쪽 문자열을 뒤집어 오른쪽을 구성하는 방식으로 풀이했다.

 

먼저 딕셔너리를 이용하여 각 알파벳의 개수를 셌다.

만약, 어떤 알파벳이 두 가지 이상 홀수개라면 팰린드롬을 출력할 수 없으므로 I'm Sorry Hansoo를 출력한다.

이제 홀수개의 알파벳이 1가지 존재하거나 없는 경우만 남을 것이다.

 

홀수개의 알파벳이 존재한다면 center라는 변수에 저장해준다.

그 다음 모든 알파벳의 개수를 반으로 나눈 만큼 이어붙여 팰린드롬의 왼쪽 부분을 구성했다.

이제 center를 이어붙이고 왼쪽 부분을 뒤집어 오른쪽 부분도 만들어준 뒤 출력하면 된다.

 

사전순으로 앞서는 문자열을 먼저 출력해야 하므로 딕셔너리에 저장된 key값(알파벳)을 정렬해준 뒤 구성했다.

 

import sys
input = sys.stdin.readline

d = dict()
s = input().rstrip()
for i in s:
    if d.get(i) == None:
        d[i] = 1
    else:
        d[i] += 1
        
center = ''
for k,v in d.items():
    if v % 2 == 1:
        if len(center)>0:
            print("I'm Sorry Hansoo")
            break
        center = k
else:
    ans = ''
    for k,v in sorted(d.items()):
        ans+=k*(v//2)
    ans += center + ans[::-1]
    print(ans)