2022-07-18 @이영훈
접근방법
문자열에서 특정 문자가 홀수인 경우는 최대 1개일 때만 팰린드롬을 만들 수 있습니다.
•
AABBB는 문자가 홀수인 경우는 B 하나 뿐입니다. 이 때는 팰린드롬(ABBBA)을 만들 수 있습니다.
•
AAABBB는 문자가 홀수인 경우가 2가지입니다. 이 때는 팰린드롬을 만들 수 없습니다.
그래서 다음을 알 수 있습니다.
1.
문자 길이가 짝수인 경우는 모든 문자가 짝수 번 등장합니다.
2.
문자 길이가 홀수인 경우는 한 문자만 홀수 번 등장하고, 나머지 모든 문자는 짝수 번 등장합니다.
문자 길이가 짝수인 경우는 사전순으로 앞쪽에 오는 문자열들을 절반 번 (나누기 2) 반복하고, 뒤집어서 뒤쪽에 이어붙이면 팰린드롬이 완성됩니다.
문자 길이가 홀수인 경우는 사전순으로 앞쪽에 오는 문자열들을 절반 번 (나누기 2) 반복하고, 홀수번 나오는 문자열을 이어붙이고, 앞쪽의 문자열을 뒤집어서 이어붙이면 팰린드롬이 완성됩니다.
파이썬 구현
string = input()
# 맵(map)에 각 문자열이 몇 번 등장했는 지 기록합니다.
characters = dict()
for char in string:
if characters.get(char, 0) == 0:
characters[char] = 1
else:
characters[char] += 1
# 문자열을 오름차순 정렬하고 홀수번 등장한 문자를 기록합니다.
# 이 때 홀수번 등장한 문자가 2번 이상이면 I'm Sorry를 출력하고 종료합니다.
keys = sorted(characters.keys())
odd_char = ""
for key in keys:
if characters.get(key) % 2 == 1:
if odd_char == "":
odd_char = key
else:
print("I'm Sorry Hansoo")
exit(0)
# 사전순으로 문자열들을 절반 번 반복하고
# 홀수번 나오는 문자열이 있다면 이어붙이고,
# 앞쪽의 문자열을 뒤집어서 이어붙여서 팰린드롬을 만듭니다.
answer = ""
temp = ""
for key in keys:
count = characters[key] // 2
temp += key * count
characters[key] = int(characters[key] / 2) # 홀수번 등장하는 경우가 있기 때문에 int 함수로 내림합니다.
answer += temp
if odd_char != "":
answer += odd_char
answer += temp[::-1]
print(answer)
Python
복사