[백준] 1213: 팰린드롬 만들기

구현

문제:팰린드롬 만들기

  1. 팰린드롬을 만드려면 각 알파벳의 갯수가 홀수 개인 알파벳이 두개 이상 있으면 안된다.
    예를 들어 ABB는 만들 수 있지만 AB는 만들 수 없다.
  2. 정답이 여러개일 경우에는 사전순으로 출력해야한다.
    그래서 리스트를 정렬해야한다.
  3. 알파벳의 갯수가 홀수인 알파벳이 있다면 그 중 하나는 팰린드롬의 가운데에 있고 남은 알파벳은 앞뒤 배치하면 된다.
    없으면 그냥 앞뒤 배치
    이 때 알파벳갯수 // 2 만큼 answer에 추가하고 거꾸로 출력해서 더한다.
import sys
from collections import defaultdict
input = sys.stdin.readline
lst = list(sys.stdin.readline().rstrip())
# 소팅 안하면 순서대로 안나옴
lst.sort()
count = defaultdict(int)
for i in lst:
	count[i] += 1
exitCnt = 0
answer = []
mid = ''
for i in count:
	# 두개 이상이면 팰린드롬 만들 수 없음
	if count[i] % 2 == 1:
		exitCnt += 1
        # 가운데에 들어갈 수 
		mid = i
	if exitCnt >= 2:
		print("I'm Sorry Hansoo")
		exit()
     # 갯수 // 2개 만큼만 answer에 추가 
	for j in range(count[i] // 2):
		answer.append(i)
end = list(reversed(answer))
if mid == '':
	print(''.join(answer) + ''.join(end))
else:
	print(''.join(answer) +mid + ''.join(end))

좋은 웹페이지 즐겨찾기