[리트코드/leetcode/python] 409. Longest Palindrome

이미지를 누르면 문제 링크를 보실 수 있습니다.

 

주어진 문자열 s를 이용해서 만들 수 있는 가장 긴 팰린드롬을 구하는 문제입니다.

문자열 s는 대문자와 소문자가 구분해서 주어지고 만들어 질 수 있는 가장 긴 팰린드롬의 길이를 답으로 출력하면 됩니다.

 

처음에 접근했던 방법은 Discussion에서 해당 코멘트를 봤습니다.

한 유저가 남긴 코멘트였는데, 해시맵을 사용하면 된다고 해서 바로 딕셔너리를 생각해봤습니다.

주어진 문자열에서 문자가 나온 횟수를 value로 저장하고, 해당 문자를 key값으로 저장하는 딕셔너리를 생각해본다면,

가장 긴 팰린드롬의 길이는 짝수의 횟수를 가진 key값과 홀수값 중에서 최댓값을 가진 key값의 구성으로 만들어지겠다라는 것이 추론됩니다.

예를 들어서 설명해볼까요?

"aabbsserrr" 이라는 문자열이 있다고 하면, 이 문자열에서 만들 수 있는 가장 긴 팰린드롬 중 하나는 "absrrrsba"로, 길이는 9가 됩니다.

이 문자열에서 짝수번 나온 a,b,s 의 횟수를 더하고(2+2+2=6번) 홀수번 나온 e,r 중에서 최댓값의 홀수를 가진 r(3번)을 더하면 9가 되는 것을 알 수 있는데요, 해당 로직대로 코드를 짜니까 오류를 내뿜는 테스트 케이스가 나왔습니다.

Disussion에서도 똑같은 테스트케이스로 오류를 발견한 유저가 있었는데요, 해당 테스트케이스는 다음과 같습니다.

생각해보면, 제가 간과한 부분이 있었어요.

바로 홀수번 나온 알파벳이라도 그 중에서 일부를 활용할 수 있다는 사실을 말이죠. 예를 들어서 c라는 문자가 5번 나오면, 저는 이 ccccc중에서 c를 4번 사용해서 팰린드롬을 만들 수 있다는 뜻이었습니다.

해당 케이스를 고려한 코드는 아래와 같습니다.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        
        answer = 0
        alpha = {}
        for c in s:
            if c not in alpha:
                alpha[c] = 1
            else:
                alpha[c] += 1

        odd_exist = False
        max_odd = 0
        for value in  alpha.values():
            if value % 2 == 0:
                answer += value
            else:
                max_odd = max(max_odd,value)
                odd_exist = True
                answer += ( value -1 )
        if odd_exist:
            answer += 1
        return answer

처음 for문은 alph라는 딕셔너리에 문자열 s에 포함되어 있는 알파벳 횟수를 키,값 형태로 저장해 주는 작업입니다.

odd_exist 라는 변수를 false로 초기화해주고, alpha를 돌면서, value값이 짝수이면 그대로 answer에 더해주고, value가 홀수라면, 최대 홀수번을 뜻하는 변수 max_odd 와 비교해서 갱신해주고, answer에 value-1 을 더해줍니다.

(value-1) 을 더해주는 이유는 어차피 홀수번 나오는 알파벳을 활용해야 하는데, 홀수값 중에서 최대 홀수값을 1번만 제외하고는 다 해당 홀수값보다 1 작은 짝수를 더해줘야 최대가 나오기 때문입니다.

odd_exist 변수를 넣어준 이유도, 최대 홀수값을 가질 때에도 (value-1)을 해주므로, 한번은 최대홀수값을 더해줘야 하는 원칙에 위배되기 때문에 다시 1을 더해줌으로써 최대홀수값을 더한 효과를 하기 위함입니다.

 

리트코드에 있는 다른 코드도 한 번 살펴보시죠.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        ans = 0
        count = collections.Counter(s)
    
        for c in count.values():
          ans += c if c % 2 == 0 else c - 1
    
        hasOddCount = any(c % 2 == 1 for c in count.values())
    
        return ans + hasOddCount

이상 Longest Palindrome 문제를 정리해봤습니다.