[PCCP] 해시 - 팰린드롬 길이 | 파이썬

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

해시 - 팰린드롬 길이

앞서 공부한 해시을 사용해 팰린드롬 길이 문제를 풀어보겠다.

---

문제

문자열이 주어지면 해당 문자열의 문자들을 가지고 만들 수 있는 최대길이 팰린드롬을 만들고 그 길이를 구하세요. 문자열은 소문자로만 이루어져 있습니다.
만약 "abcbbbccaaeee" 가 주어진다면 만들 수 있는 가장 긴 팰린드롬은 "ebbcaaacbbe"이고 답은 11입니다.

---

입출력 예

입력(s)	출력(answer)
"abcbbbccaaeee"	11
"aabbccddee"	10
"fgfgabtetaaaetytceefcecekefefkccckbsgaafffg"	41
"aabcefagcefbcabbcc"	17
"abcbbbccaa"	9

---

제한사항

• s의 길이는 100을 넘지 않습니다.

---

코드

from collections import Counter

def solution(s):
    sH = Counter(s)
    odd = 0

    for key in sH:
        if sH[key] % 2 == 1:
            odd += 1
    
    return len(s) - odd + 1 if odd > 0 else len(s)

print(solution("abcbbbccaaeee"))
print(solution("aabbccddee"))
print(solution("fgfgabtetaaaetytceefcecekefefkccckbsgaafffg"))
print(solution("aabcefagcefbcabbcc"))
print(solution("abcbbbccaa"))

---

풀이

위키백과 - 회문
회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

주어진 s의 원소들을 가지고 팰린드롬의 최대길이를 만들어야 한다.
우선, 원소들 중 짝수의 빈도 수를 가지는 원소들은 무조건 팰린드롬 길이에 포함된다.
이때 홀수의 처리는 가장 큰 홀수를 제외하고는 -1를 한 후, 팰린드롬 길이에 포함할 수 있다.

따라서 식은 len(s) - 홀수들의 수 + 1이다.
+1을 하는 이유는 가장 큰 홀수는 -1을 하지 않기 때문이다.

1. Counter를 이용해 sH에 s의 문자 빈도 수를 센 Counter 객체를 반환
2. 문자 빈도 수가 홀수라면 odd =+ 1
3. 홀수의 개수를 다 센 후,
   • odd > 0인 경우(홀수 존재) : 아까 세운 식을 이용해 return len(s) - odd + 1
   • odd = 0인 경우(홀수 미존재) : return len(s)