[python] 백준 1213번-팰린드롬 만들기

SJ H·2022년 6월 7일

구현 알고리즘

알고리즘 스터디(발표 자료)

목록 보기

7/9

문제 - 팰린드롬 만들기

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

문제 설명

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

🤨풀이를 어떻게 생각했는가?

1. 문제의 조건

영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.
첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

2. 고민 과정

팰린드롬은 좌우가 똑같아야 한다 -> 홀수가 두개 이상이면 성립되지 않는다. ex) ABCDBA
사전 순으로 앞서는 것을 출력한다 -> 입력값을 정렬할 필요가 있다.
짝수라면 앞, 뒤 리스트를 만들어 마지막에 붙이면 될 것 같다.
위 세 조건을 만족한다면 답이 나올것 같다.

3. 주요 포인트

홀수가 2개 이상인지 확인할 것.
입력값이 정렬되어 사전순으로 출력이 가능할 것.

4. 구현 과정

dict 형태로 현재 알파벳이 뭐가 있는지, 몇개인지를 넣는다. -> Counter 이용
입력값의 알파벳 수를 구해서 홀수가 2개 이상인지 파악해야 한다. -> Counter.items() 이용
홀수가 1개라면, 현재 홀수의 알파벳을 저장해준다. -> 나중에 붙여주기 위함.
입력받은 값을 정렬한 후, FOR문을 통해 가지고 있는 알파벳을 result에 넣는다.
이때, 입력받은 값의 길이의 몫을 구해 현재 알파벳에 곱해준다.
마지막에 홀수 알파벳과, 역순으로 바꾼 앞 리스트를 붙여준다.

import collections
import sys

word = sys.stdin.readline().rstrip()
check_word = collections.Counter(word)
cnt = 0
result = ''
mid = ''
for k, v in list(check_word.items()):
    if v % 2 == 1: #홀수라면
        cnt += 1
        mid = k #중간에 들어갈 값으로 저장
        if cnt >= 2: #홀수가 2개이상이면 팰린드롬이 될 수 없다!!
            print("I'm Sorry Hansoo")
            exit()

for k, v in sorted(check_word.items()): #정렬을 통해 사전순으로 for문을 돌게함
    result += (k * (v // 2)) #정확히 절반으로 나뉜 문자열을 만들어야 하므로 현재 갯수를 2로 나눠줌
print(result + mid + result[::-1]) # 앞+중간+뒤 를 더해 문자열 출력