[백준] 1213 팰린드롬 만들기 (실버3)

문제요약

나의 코드 및 설명

string = list(input())

alpha = [0] * 26

string.sort() #문자열 오름차순으로 정렬

for i in range(len(string)):
    alpha[ord(string[i])-65] += 1 #알파벳 개수를 저장

odd_cnt = 0
odd_string = ""
total_string = ""
for i in range(len(alpha)):
    if alpha[i] % 2 == 1: #문자열의 알파벳 개수가 홀수라면,
        odd_cnt += 1 #홀수 카운트 + 1
        odd_string += chr(i+65) #홀수인 알파벳 저장 (홀수개인 알파벳이 가운데에 위치해야 하므로)
    total_string += (alpha[i] // 2) * chr(i+65) #전체 알파벳을 절반 개수만 저장 (홀수개인 알파벳도 포함)
    #예를들어 AAABB의 경우, odd_string 에 A 저장되고
    #                   total_string에 AB가 저장됨

if odd_cnt <= 1: #홀수개인 알파벳의 개수가 1보다 작거나 같으면 팰린드롬 가능
    print(total_string + odd_string + total_string[::-1])
else:
    print("I'm Sorry Hansoo")

피드백

처음엔 백트래킹으로 풀려다가 실패했다. 결국 구글링을 통해 다른 사람의 코드를 참고했는데, 풀이를 보고 좀 충격먹었다. 이런 생각을 하다니 ... 우선 문자열이 주어졌을 때, 그 문자열에 등장하는 문자의 개수가 홀수 개인 것이 2개 이상이라면 백트래킹이 불가하다.(ex. AAABBB) 나도 몰랐었는데, 이 문제를 통해 정확히 정리할 수 있었다..  그리고 문자의 개수가 홀수 개인 문자가 문자열의 중앙에 반드시 위치해야 하므로, odd_string에 가운데에 위치할 문자(문자의 개수가 홀수 개인 문자)를 저장한다. for문을 계속 수행하면서 total_list에 모든 문자를 2로 나눈 몫의 개수만큼 저장한다.(ex. AABBB이면, odd_string에 B 저장. total_string에 AB 저장. 이 때, B의 개수는 3개이지만 2로 나눈 몫의 개수인 1개만큼 total_string에 저장하면 된다.) 출력할 때, total_string, odd_string, total_string[::-1]을 이어 붙여서 출력한다. (앞에서 문자열 리스트를 오름차순 정렬해주었으므로 사전순으로 출력된다.)