백준 1213) 팰린드롬 만들기 정리 (python)

간단한 팰린드롬 문제를 무작정 구현하려다 많이 고생하여서

팰린드롬을 만드는 알고리즘을 이해하고자 블로그 글을 작성합니다.

1. 팰린드롬이란?

거꾸로 읽어도 똑같은 문장이나 단어를 말한다.

예를틀면 eye,hannah, AABCBAA 같은 단어가 있다.

좌우대칭이라고 생각하면 좋다.

2. 팰린드롬이 될 수 있는 단어의 조건은?

-> 문자의 개수가 홀수인 문자는 하나 이하여야 한다.

팰린드롬은 좌우 대칭이어야 하므로 홀수개인 문자는 하나만 중앙에 둘 수 있다.

예를 들어 eye는 e는 2개, y가 1개로 홀수인 문자가 y 뿐이라 팰린드롬이지만

eyde면 e는 2개, y는 1개, d도 1개로 홀수인 문자가 2개나 있어서

문자의 배치를 바꿔도 팰린드롬이 될 수 없다.

 

3. 입력한 단어를 팰린드롬으로 바꾸자!

1.개수가 홀수인 문자는 중앙에 와야한다.

 

2.하지만 사전순으로 앞서는 것을 출력해야 하므로, 모두 다 중앙에 오면 오답이 나온다.

ex) AABBBCC는 ABCBCBA가 정답이다. 모두 다 중앙에 오게하면 ACBBBCA가 된다.

 

3.따라서 개수가 홀수인 문자가 있다면, 개수와 상관없이 1개만 중앙에 오게하고, 나머지는 사전순으로 정렬한다.

 

4.사전순으로 정렬한 문자들을 정방향과 역방향으로 한번씩 출력하게 하고, 중앙에 오게 한 홀수인 문자가 있다면 중간에 넣어준다.

 

구현 코드

from collections import defaultdict
string=list(input())
# 디폴트값으로 0을 갖는 defaultdict 선언
dict=defaultdict(int)
#문자별로 딕셔너리에 개수를 넣어 줌
for i in string:
    dict[i]+=1
#개수가 홀수인 문자의 개수 
holsu_count=0
#정답 리스트
ans=[]
#좌우 대칭을 진행할 문자의 리스트
pelindrom=[]
#개수가 홀수인 문자를 담은 리스트
holsu=[]
#딕셔너리에 담긴 문자들 for문
for j in dict.keys():
    #문자의 개수의 절반만큼 팰린드롬 리스트에 담음
    for i in range(dict[j]//2):
        pelindrom.append(j)
    #문자의 개수가 홀수인 문자는 중앙에 둘 문자 하나만 홀수 리스트에 담음
    if dict[j]%2!=0:
        holsu_count+=1
        holsu.append(j)
#홀수가 두개 이상 있으면 팰린드롬 불가
if holsu_count>1:
    print("I'm Sorry Hansoo")
else:
    #사전순 출력을 위한 정렬
    pelindrom.sort()
    #홀수 개수인 문자가 있을 때
    if len(string)%2!=0:
        #좌우대칭으로 출력하고 중앙에 홀수 리스트를 넣어줌
        ans=pelindrom+holsu+pelindrom[::-1]
    else:
        ans=pelindrom+pelindrom[::-1]
    for k in ans:
        print(k,end='')

구현 코드 설명

1. defaultdict를 사용하여 0으로 초기화가 되어있는 딕셔너리를 사용한다.

문자값인 i 마다 딕셔너리에 key로 개수를 더해준다.

2. 딕셔너리의 key들을 이용하여 중앙에 둘 문자와 정방향과 역방향으로 출력할 문자를 리스트에 넣어준다.

3. 개수가 홀수인 문자가 2개 이상이면 정답을 출력할 수 없으므로 예외처리를 해준다.

   개수가 홀수인 문자가 1개 있으면 중앙에 문자를 출력해주고 없으면 그냥 팰린드롬 형식으로 출력해준다.