백준 1213 팰린드롬 만들기

문제 URL : https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

문제 접근법 : 

문자열을 입력받아서 팰린드롬을 만드는 문제입니다. 그것도 사전순으로 가장빠르게

 

입력받은  팰린드롬으로 만들수있다고 가정할때

문자열길이가 홀수냐 짝수냐에 따라 나눕니다.

짝수인경우 문자열

모든문자가 짝수개입니다. 즉 홀수개가 하나라도 존재하면 만들수가없죠

그리고 A~Z까지 있는것들만 그개수/2 개만큼 문자열을 합친후

다합친것의 문자열을 뒤집어서 한번더 합치면 팰린드롬이 만들어집니다.

홀수인경우는 

반드시 홀수개가 1이고 그이상이면 만들수 없습니다. 그리고

마찬가지로 A~Z까지 있는것들의 개수/2 개만큼 문자열 합친후

다합친다음 + 홀수개인문자하나와 + 합친것의 뒤집은것을 출력하면 끝납니다.

 

소스코드:

import sys
from collections import Counter

        

s= input()
def pallin(s):
    no = "I'm Sorry Hansoo"
    m = Counter(s)
    m2 = sorted(m.items())
    if len(s)%2==0:
        res=[]
        for k,val in m2:
            if val%2:
                print(no)
                return
            res.append(k*(val//2))
        res+=list(reversed(res))
        print(''.join(res))
    else:
        res =[]
        cnt=0
        for k,val in m2:
            if val%2:
                cnt+=1
                if cnt>1:
                    print(no)
                    return
        t=''
        for k,val in m2:
            if val%2:
                t=k
                if val>1:
                    res.append(k*(val//2))
                    continue
            res.append(k*(val//2))
        res+=list(t)+list(reversed(res))
        print(''.join(res))    
pallin(s)

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.