[백준 / Python] 1213번 팬린드롬 만들기

문제

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

1213번: 팰린드롬 만들기

 

---

풀이 코드

alcnt = [0] * 30
# A가 65이므로 -65를 할 것 ord() chr()
input = input()
for i in input:
    alcnt[ord(i)-65] += 1
cnt = 0
for i in range(30):
    if alcnt[i] % 2 == 1:
        cnt += 1
        oddindex = i
answer = ""
if cnt == 1:
    alcnt[oddindex] -= 1
    lts = chr(oddindex+65)
    
if cnt > 1:
    print("I'm Sorry Hansoo")
else:    
    for i in range(30):
        answer += (alcnt[i] // 2) * chr(i+65)
    data = answer[::-1]
    if cnt == 1:
        print(answer + lts + data)
    else:
        print(answer + data)

 

문제 설명

이번 문제는 문자열이 주어지면 사전순으로 가장 빠른 팬린드롬을 만드는 것이다. 

 

팬린드롬이란 뒤집어도 같은, 즉 앞에서 읽는 문자열과 뒤에서 읽는 문자열이 같은 문자열이다. 

예를 들어, "ABAACAABA", "QQQ", "GHHG" 등이다. 

위 단어들은 뒤에서 부터 읽어도 같기에 팬린드롬이다. 

 

팬린드롬을 만들지 못하는 경우는 I'm Sorry Hansoo를 출력한다. 

---

풀이 설명

먼저, 아스키코드 변환을 이용하여 문자열들을 alcnt 리스트에 계수정렬하였다. 

( chr(65) -> 'A' , ord('A') -> 65)

 

계수정렬을 했기에 주어진 문자열에서 각 알파벳 대문자들이 몇개가 주어졌는지 알 수 있는 상태이다. 

팬린드롬은 홀수개인 알파벳이 2개 이상이라면 만들지 못하니, 이 경우에는 I'm Sorry Hansoo를 출력한다. 

 

그렇다면 홀 수 개수인 알파벳이 0개인 경우와 1개인 경우가 있다.

0개인 경우 사전순(A, B, C ...)으로 반복문으로 alcnt를 순회하며 각 개수의 절반만큼의 알파벳을 answer에 붙힌다.

그 후 answer와 뒤집은 answer (answer[::-1])을 붙힌 뒤 출력한다. 

 

1개인 경우 홀 수 개수인 알파벳을 alcnt 리스트에서 하나를 빼고 이를 기억한다. (lts 변수)

그 뒤 마찬가지로, 사전순(A, B, C ...)으로 반복문으로 alcnt를 순회하며 각 개수의 절반만큼의 알파벳을 answer에 붙힌다.

그 후 answer와 lts와 뒤집은 answer (answer[::-1])을 붙힌 뒤 출력한다.