[Greedy]99클럽 코테 스터디 36일차 TIL + 0409-longest-palindrome

409. Longest Palindrome

Easy

---

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

<내 코드>

- 1단계

class Solution:
    def longestPalindrome(self, s: str) -> int:
        s_hash = {}

        for c in s:
            if c not in s_hash:
                s_hash[c] = 1
            else :
                s_hash[c] += 1

    # 직접 값을 입력하는 방식
        string = deque()
        sorted_hash = dict(sorted(s_hash.items(), key=lambda item: item[1]))
        print(sorted_hash)

        if len(s_hash) == 1:
            for _ in range(sorted_hash[s[0]]):
                string.append(s[0])
            return len(string)

        for key, value in sorted_hash.items():
            if value == 1 and not string :
                string.append(key)
            elif value != 1:
                for i in range(0, value, 2):
                    print(i)

                    string.appendleft(key)
                    string.append(key)
        print(string)

        return len(string)

* 이 단계에는 string 이라는 deque 를 이용했음

하지만 실질적으로 팰린드롬을 만들 필요가 전혀없음! 문제의 핵심로직은 팰린드롬이 최대 몇개의 길이까지 가능하냐임

단순하 연산으로 쉽게 접근이 가능함

* 하지만 딕셔너리로 각 값이 몇개인지 바로 찾아서 넣은것은 뿌듯함

- 2단계

# 2번째 방식
class Solution:
    def longestPalindrome(self, s: str) -> int:
        s_hash = {}

        for c in s:
            if c not in s_hash:
                s_hash[c] = 1
            else :
                s_hash[c] += 1

        s_hash = dict(sorted(s_hash.items(), key=lambda item: item[1]))

        count = 0
        for key, value in s_hash.items():
            # if len(s_hash) == 1:
            #     count += s_hash[key]
            #     return count

            if value == 1 and count == 0:
                count += 1
            elif value != 1:
                if value % 2 == 1 : #홀수이면
                    value -= 1
                    odd_found = True  # 홀수가 있음을 표시
                count += value


        if odd_found:
                count += 1  # 홀수가 하나라도 있으면 중앙에 하나를 추가 가능
        return count

* 이 단계에서 연산 방식으로 바꿨음

하지만 여전히 문제는 각 Edge case 에 대한 모든것을 핸들링하기에는 어려움이 있었음

"ccc"
"ccd"
"bananas"
"ababababa"

이 4가지의 경우에 매번 하나씩 예외처리로서 해결하는데 곤란함이 있었음

1개만 있는 경우에 대한 처리를 해결했지만, 하나의 값이 3개가 있을 떄 에대한 처리도 어려웠음

결국에 GPT 의 도움을 받음

- 3단계

class Solution:
    def longestPalindrome(self, s: str) -> int:
        s_hash = {}

        for c in s:
            if c not in s_hash:
                s_hash[c] = 1
            else :
                s_hash[c] += 1
        print(s_hash)
        odd_found = False

        count = 0
        odd_found = False

        for value in s_hash.values():
            if value % 2 == 0:
                count += value  # 짝수 개수는 그대로 추가
            else:
                count += value - 1  # 홀수 개수에서 1을 빼고 추가
                odd_found = True  # 홀수가 있음을 표시

        if odd_found:
            count += 1  # 홀수가 하나라도 있으면 중앙에 하나를 추가 가능
        return count

* 위와같이 각 문자가 짝홀수 여부에 따라서 달리판단됨

=> 짝수라면은 짝수 갯수 그 자체를 모두 count 에 더함

=> 홀수라면은 -1을 해서 짝수를 뺴줌

* 1개의 문자라면

count 연산 때 -1을 하면 0이 되어서 의미는 없음,마지막 odd_found로 별도 처리를 해줌

만약 1개의 문자가 여러개라고 하더라도 odd_found 로 단 한번만 체크해서 단 한번만 연산하기 때문에 이 부분도 해결이 됨

* 실질적으로 존재하느냐가 아니라 무엇을 요규하느냐

문제에서 팰린드롬을 요구하길래 그럴듯한 것을 만들어야한다고 생각함

핵심 로직이 무엇인지 고민해보자

<모범사례>

from collections import Counter

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = Counter(s)
        length = 0
        odd_found = False

        for value in count.values():
            if value % 2 == 0:
                length += value
            else:
                length += value - 1
                odd_found = True

        return length + 1 if odd_found else length

- Count 로 보다 쉽게 이용이 가능함

<보충학습>

1. 실무에서의 사용

- 실무에서는 해시맵으로 빈도 계산은 자주 이용이 됨

예컨데

- 로그에서 특정 이벤트의 발생빈도 계산용!

- 마케팅 고객 리뷰 분석할 때 긍정적, 부정적 피드백 단어 빈도 계산

- 웹 크롤링

2. collections.Counter 사용하기

from collections import Counter

# 문제 1: 가장 빈도수가 높은 문자 찾기
s1 = Counter("hello")
print(s1.most_common(2))

# 문제 2: 두 문자열의 공통 문자 찾기
s2_1 = Counter("apple")
s2_2 = Counter("ample")

s2_3 = s2_1 & s2_2 # 교집합
print(s2_3)
# 문제 3: 단어 빈도수 계산
# s3 = Counter("this is a test this is only a test")
# s3.pop(' ')

# pop 대신에 분리하는게 더 좋음
s3= Counter("this is a test this is only a test".split())
print(s3)

print(s3)

# 문제 4: 아나그램 찾기
s4_1 = Counter("listen")
s4_2 = Counter("silent")

if s4_1 == s4_2 :
    print(True)
else : print(False)

 

- Counter 기본 개념

collections.Counter 요약 정리

1. Counter 생성

• 사용법: 반복 가능한 객체(문자열, 리스트 등)에서 각 요소의 빈도수를 계산하여 Counter 객체를 생성.

  from collections import Counter
  count = Counter('example')  # Output: Counter({'e': 2, 'x': 1, 'a': 1, 'm': 1, 'p': 1, 'l': 1})

2. 요소의 빈도수 조회

• 사용법: 특정 요소의 빈도수를 확인.

  count['e']  # Output: 2
  count['z']  # Output: 0 (존재하지 않는 요소는 0 반환)

3. 가장 빈도 높은 요소 찾기

• 사용법: most_common(n)을 사용하여 가장 빈도가 높은 요소 n개를 반환.

  count.most_common(2)  # Output: [('e', 2), ('x', 1)]

4. Counter 간 연산

• 사용법: Counter 객체끼리 더하거나 빼는 연산이 가능.

  count1 = Counter('hello')
  count2 = Counter('world')
  combined = count1 + count2  # Output: Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, 'w': 1, 'r': 1, 'd': 1})

5. 요소 삭제

• 사용법: 특정 요소를 삭제하거나 개수를 조정.

  del count['e']  # 'e'를 삭제

6. 빈도수가 0인 요소 제거

• 사용법: + 연산으로 빈도수가 0 이하인 요소를 제거.

  count = Counter({'a': 3, 'b': -1, 'c': 0})
  cleaned = +count  # Output: Counter({'a': 3})

7. Counter를 리스트나 사전으로 변환

• 사용법: elements()는 요소를 반복하여 반환, dict()는 사전으로 변환.

  list(count.elements())  # 요소를 빈도만큼 반복: ['a', 'a', 'a']
  dict(count)  # Counter를 사전으로 변환: {'a': 3, 'b': -1, 'c': 0}

요약

• Counter 생성: Counter('data')
• 빈도 조회: count['a']
• 가장 빈도 높은 요소: count.most_common(1)
• Counter 연산: count1 + count2
• 요소 삭제: del count['a']
• 0 이하 제거: +count
• 리스트/사전 변환: list(count.elements()), dict(count)

이 요약본을 사전처럼 참고하며, 필요한 기능을 즉시 확인하고 사용할 수 있습니다.