LeetCode #409 - Longest Palindrome(가장 긴 팰린드롬) 풀이

문제

문제에서 등장하는 팰린드롬은 문자열의 가운데를 기준으로 하여 2개로 나누었을 때, 첫 번째 문자열과 두 번째 문자열의 역순이 같은 문자열을 말하며 다음과 같이 규칙성을 정리해보았다.

1. 문자열을 구성하는 문자의 개수가 모두 짝수인 경우 모든 문자를 팰린드롬으로 배치 가능 ex) 'aabbcc' -> 'aabbcc'
2. 문자열을 구성하는 문자의 개수 중 홀수가 포함되어 있는 경우 개수가 홀수인 문자를 짝수로 활용하고, 가운데에 홀수인 문자로 하여 팰린드롬으로 배치 가능 ex) 'aaabbbccc' -> 'abcccba'

따라서. 문자열을 구성하는 문자의 개수가 홀수인 경우 이를 짝수로 만들고, 문자열의 가운데에 끼워줄 홀수 개의 문자 1개를 나중에 더하는 방식으로 접근하였다.

풀이

딕셔너리 및 변수 초기화

문자열을 구성하는 문자의 개수를 파악하여 딕셔너리에 저장한다. 그리고 문자 중에 홀수가 있는지 파악하기 위한 변수를 정의하고, 아직까지는 없다는 의미인 0으로 초기화한다.

counters = {c: s.count(c) for c in s}
is_exist_odd = 0

문자의 개수 파악 및 변경

반복문을 통해 딕셔너리의 key, value를 순차적으로 불러오고, 현재 value가 홀수인 경우 해당 value를 짝수로 만든다. 그리고, 홀수개인 문자가 존재하므로 is_exist_odd을 1로 변경한다.

for character, count in counters.items():
    if count % 2 == 1:
        counters[character] = count - 1
        is_exist_odd = 1

최종 결과 반환

위의 과정을 통해 전부 짝수가 된 딕셔너리의 value를 모두 합산한 후, 홀수개인 문자를 가운데에 추가하기 위해 is_exist_odd을 더한다.

return sum(list(counters.values())) + is_exist_odd

전체 코드

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counters = {c: s.count(c) for c in s}

        is_exist_odd = 0
        for character, count in counters.items():
            if count % 2 == 1:
                counters[character] = count - 1
                is_exist_odd = 1

        return sum(list(counters.values())) + is_exist_odd