백준 :: 1213번 팰린드롬 만들기 (Python)

문제 링크

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

1213번: 팰린드롬 만들기

 

접근 방식

https://blog.jujuwon.dev/103

백준 :: 1254번 팰린드롬 만들기 (Python)

위 문제와 왜인지 모르게 문제 이름이 똑같은데.. 숫자라도 붙여주지 ..

문제를 풀면서 사소한 부분에서 삽질을 굉장히 많이 했던 문제입니다.

먼저 팰린드롬을 만들 수 있는 경우를 다양하게 생각해보면서 조건을 생각해내었습니다.

예제로 나온 문자열들은 AABB, AAABB, ABACABA, ABCD 인데,

이 예제 문자열들을 가지고 경우의 수를 생각해보았습니다.

우선 팰린드롬을 만들 수 있는 경우와 없는 경우를 나누어봅시다 !

• AABB → 가능 A 2개, B 2개
• AAABB → 가능 A 3개, B 2개
• ABACABA → 가능 A 4개, B 2개, C 1개
• ABCD → 불가능 A 1개, B 1개, C 1개, D 1개

위 예제를 통해 생각해보면 홀수 개 있는 특정 문자가 1개 일때까지만

팰린드롬을 만들 수 있다는 걸 알 수 있습니다.

단순히 생각해보아도 짝수개 존재하면 어떤 식으로든 대칭을 만들 수 있고

홀수개 있다면 문자 사이에 껴넣는 식으로 가능한데,

홀수개 있는 문자가 여러개 있다면 대칭을 만드는 것이 불가능하다는 걸 알 수 있습니다.

그래서 다음과 같이 접근했습니다.

1. 문자마다 등장한 횟수를 저장.
   1. 홀수번 등장한 문자가 1개 초과하는 경우 I’m Sorry Hansoo 출력
   • 딕셔너리로 저장하고 Key 를 sorting 하기 (사전순 고려)
2. 모든 문자가 짝수번 등장한 경우
   1. 저장된 문자 횟수의 절반 만큼 뽑아서 문자열을 만든다.
   2. 만든 문자열을 뒤집어서 추가로 붙인다.
3. 홀수개인 문자가 하나 있는 경우
   1. 짝수인 경우와 동일
   2. 가운데에 홀수개인 문자 하나를 넣어줌

풀이 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

count = {}
answer = []
name = list(input())
for n in name:
    if count.get(n, 0) == 0:
        count[n] = 1
    else:
        count[n] += 1

keys = sorted(count.keys())

odd_flag = False
odd_char = ''

for key in keys:
    if count[key] % 2 != 0:
        if odd_flag:
            print("I'm Sorry Hansoo")
            exit(0)
        else:
            odd_flag = True
            odd_char = key

answer = ''
for key in keys:
    answer = answer + key * int(count[key] // 2)
appendix = answer[::-1]
if odd_flag:
    answer += odd_char
answer += appendix

print(answer)

삽질의 흔적..

끝.