[백준] 팰린드롬 만들기 1213 (Python)

문제 링크

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

1213번: 팰린드롬 만들기

나의 풀이

• 우선 팰린드롬을 만들 수 있는 문자열의 조건에 대해 살펴보겠습니다.
  • 전체 길이가 짝수인 문자열에서는 빈도수가 홀수인 알파벳이 있어선 안됩니다.
    • ex) "ABCC
  • 전체 길이가 홀수인 문자열에서는 빈도수가 홀수인 알파벳이 하나까지는 허용됩니다.
  • 그러나 전체 길이가 짝수인 경우 빈도수가 홀수인 알파벳이 하나는 허용되지만, 빈도수가 홀수인 알파벳이 하나만 나올 수 없습니다. 홀수 + 홀수 = 짝수 이기 때문입니다. 즉, 빈도수가 홀수인 알파벳 개수를 따질 때는 빈도수가 홀수인 알파벳은 하나 이하만 허용됩니다.
• 저는 빈도수 확인을 위해 Counter를 사용했습니다.
• 그리고 문제 조건 중 정답이 여러 개인 경우 사전 순으로 앞서는 것을 출력해야 하기 때문에 문자열을 list로 변환 후 정렬한 뒤 진행했습니다.
• 위의 조건을 만족해 팰린드롬을 만들 수 있는 알파벳의 경우에만 팰린드롬을 만들어줍니다.
• 빈도수가 홀수인 알파벳은 팰린드롬 문자열의 가운데 위치해야 합니다.
• 팰린드롬 만드는 방법
  1. for문으로 문자열 list를 돕니다. 이때, for문의 step은 2로 합니다.
     • input = "abbaa" 이면, sorting_list = [a, a, a, b, b]가 됩니다.
     • 빈도수가 홀수인 알파벳에 대해 예외처리를 해줍니다.
       
       • 처음으로 빈도수가 홀수인 알파벳을 만날 경우 팰린드롬 문자열에 추가하지 않고, 빈도수만 -= 1을 해줘서, 다음부터는 팰린드롬 문자열에 추가되게 해줍니다.
  2. 만들어진 절반의 팰린드롬을 tmp변수에 저장합니다.
  3. 절반의 팰린드롬을 완성한 뒤, 빈도수가 홀수인 문자열을 팰린드롬 문자열에 추가해줍니다.
  4. tmp에 저장된 문자열을 뒤집어 팰린드롬 문자열에 추가합니다.

예외처리

Code

# 팰린드롬 만들기
# https://www.acmicpc.net/problem/1213

# 팰린드롬이 되기 위해선 단어 길이가 짝수일 경우 홀수 개인 알파벳이 있으면 안됨.
# 단어가 홀수 길이면 홀수 개인 알파벳이 하나 있어도됨

from collections import Counter
import sys

word = input()
word_list = list(word)
word_list.sort()

word_count = Counter(word_list)

odd_alphabet_count = 0
odd_alphabet = ''
for alphabet in word_count:
    if word_count[alphabet] % 2 == 1:
        odd_alphabet_count += 1
        odd_alphabet += alphabet
    if odd_alphabet_count > 1:
        print("I'm Sorry Hansoo")
        sys.exit()

answer = ''

for i in range(0, len(word), 2):
    if word_count[word_list[i]] % 2 == 1:
        word_count[word_list[i]] -= 1
    else:
        answer += word_list[i]

tmp = answer[::-1]
answer += odd_alphabet
answer += tmp
print(answer)

Git

https://github.com/youngh0/Algorithm/blob/master/greedy/boj_1213.py