[백준] 1213번 팰린드롬 만들기 파이썬 정답 코드

1213번: 팰린드롬 만들기

---

1. 문제 내용

 

 

2. 접근 방식

• 팰린드롬이 가능하기 위한 조건을 고민하자
  • 모든 알파벳이 짝수 개씩 있을 경우
  • 딱 한 개의 알파벳만 홀수 개가 있고, 나머지는 모두 짝수 개씩 있을 경우

팰린드롬을 만들 수 있는지, 없는지를 알아내기 위해선 각 알파벳의 개수를 카운팅해야 한다. 따라서 key는 알파벳을, value는 해당 알파벳의 개수를 나타내는 딕셔너리를 생성할 필요가 있다.

 

• 조건을 만족할 경우, 어떤 원리로 팰린드롬을 만들까?

AAAABB가 입력문일 때, AABBAA, BAAAAB 2개의 팰린드롬이 생성되지만, 사전 순으로 앞서는 것인 AABBAA가 출력되어야 한다. 이때 AABBAA는 AAB와 BAA로 나눌 수 있다. 팰린드롬을 만드는 방법은 4개의 A 중 그 절반인 2개를, 2개의 B 중 그 절반인 1개를 연결한 것이 AAB이다. 이후엔 AAB를 거꾸로 뒤집은 BAA를 이어서 연결하면 팰린드롬이 완성된다.

만약 AAAABBC처럼 홀수 개인 알파벳 C가 존재한다면, C를 AAB와 BAA 사이에 집어 넣으면 된다.

 

 

3. 정답 코드

name = input() # Ex) AAAABBC

count = dict()
keys = sorted(list(set(name)))
odd = []
for key in keys:
    cnt = name.count(key)
    count[key] = cnt
    if cnt % 2:
        odd.append(key)

if len(odd) > 1:
    print("I'm Sorry Hansoo")

else:
    result = ''

    for key in keys: # Ex) AAB 생성
        result += key * (count[key] // 2)

    if odd: # Ex) AAB += C + BAA
        result += odd[0] + result[::-1]
    else: # Ex)AAB += BAA
        result += result[::-1]

    print(result)