99클럽 코테 스터디 38일차 TIL (Longest Palindrome) - LeetCode

말하는 감자·2024년 8월 28일
99클럽99클럽3기Stringgreedyleetcodepython그리디코딩테스트코딩테스트 준비파이썬해시해시 테이블향해99
1

99클럽 3기

목록 보기
38/42
post-thumbnail
post-custom-banner

오늘은 99클럽 코테 스터디 38일차 입니다. 이제 4일정도 남았네요.

꾸준히 했지만 여전히 전 부족합니다. 하지만 포기하면 안돼죠?

오늘 문제를 살펴보겠습니다!

1. 오늘의 학습 키워드

  • 해쉬
  • 펠린드롬
  • 그리디

2. 문제: 409. Longest Palindrome

문제

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.

3. 나의 풀이

99클럽 문제를 풀기전 아래 그림처럼 이 문제가 오늘 어떤 유형인지가 나와있습니다.

greedy 유형이라고 해서 어떻게 greedy로 접근할까? 하고 문제를 들어가보았는데 그리디가 전혀 생각이 안났습니다,,,

하지만, 문제를 다 풀고나니, 아! 이렇게 생각하면 이 문제가 그리디 알고리즘 유형이라고 할 수 있겠구나 생각이 났습니다.

그럼, 문제 한 번 접근해보겠습니다.

문제 설명

주어진 문자열 s에서 만들 수 있는 가장 긴 팰린드롬의 길이를 찾기 위해서는, 팰린드롬의 특성을 고려해야 합니다.

핵심 포인트:

  1. 팰린드롬의 구조:
    • 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 문자열입니다.
    • 문자열이 팰린드롬이 되려면, 그 문자열 내의 문자들이 중앙을 기준으로 대칭을 이뤄야 합니다.
    • 어떤 문자가 짝수 번 등장하면, 그 문자의 모든 인스턴스를 팰린드롬에 사용할 수 있습니다.
    • 어떤 문자가 홀수 번 등장하면, 그 문자의 인스턴스 중 하나를 제외한 나머지를 사용할 수 있습니다 (즉, 홀수 빈도를 가진 문자의 경우 n-1개의 인스턴스를 사용할 수 있습니다).
  2. 홀수 빈도의 문자 사용:
    • 홀수 빈도의 문자 중 하나는 팰린드롬의 중앙에 배치할 수 있습니다. 이를 통해 하나의 홀수 빈도 문자를 모두 사용할 수 있습니다.

문제 해결 단계:

  1. 문자열 s에서 각 문자의 빈도를 세어봅니다.
  2. 짝수 빈도는 그대로 팰린드롬 길이에 더합니다.
  3. 홀수 빈도를 가진 문자의 경우, 그 빈도에서 count - 1을 길이에 더해 최대 짝수를 포함시킵니다.
  4. 홀수 빈도를 가진 문자가 있다면, 팰린드롬의 중앙에 그 문자를 배치하기 위해 최종 길이에 1을 더할 수 있습니다.

예제 설명:

  • 예제 1: s = "abccccdd"
    • 빈도 수: a: 1, b: 1, c: 4, d: 2
    • 짝수 빈도 더하기: c: 4, d: 2 → 4 + 2 = 6
    • 홀수 빈도 처리: a: 1, b: 1 → 하나의 홀수 문자를 중앙에 배치할 수 있습니다.
    • 최종 길이: 6 + 1 = 7.

그럼 코드로 들어가볼까요?

코드 설명

from collections import Counter

class Solution1(object):

    def longestPalindrome(self, s):
        cnt = Counter(s)  # 문자열 s에서 각 문자의 빈도를 세는 Counter 객체 생성
        odd_cnt = 0  # 홀수 빈도의 문자가 있는지 확인하기 위한 변수 초기화

        for key, value in cnt.items():  # 각 문자와 그 빈도에 대해 반복
            if value % 2 != 0:  # 빈도가 홀수인 경우
                cnt[key] = value - 1  # 해당 문자의 빈도를 짝수로 만듦 (1을 뺌)
                odd_cnt = 1  # 홀수 빈도 문자가 있음을 표시

        return sum(list(cnt.values())) + odd_cnt  # 짝수 빈도의 문자 합 + 홀수 문자가 있었다면 1 추가

주요 요소:

  1. Counter 사용:

    cnt = Counter(s)
    • Counter는 문자열 s에서 각 문자의 빈도를 세어주는 Python의 내장 클래스입니다.
    • 예를 들어, s = "abccccdd"라면 cnt는 {'a': 1, 'b': 1, 'c': 4, 'd': 2}와 같은 구조를 가집니다.

  2. 홀수 빈도 처리:

    odd_cnt = 0
for key, value in cnt.items():
    if value % 2 != 0:
        cnt[key] = value - 1
        odd_cnt = 1
    • odd_cnt는 홀수 빈도를 가진 문자가 있는지 여부를 나타내는 변수입니다.
    • cnt.items()는 cnt에 저장된 각 문자와 그 빈도를 반복합니다.
    • 빈도가 홀수(value % 2 != 0)인 경우, 그 값을 짝수로 만들기 위해 value - 1로 수정합니다.
    • 그리고 최소 하나의 홀수 빈도가 존재함을 표시하기 위해 odd_cnt를 1로 설정합니다.

  3. 팰린드롬 길이 계산:

    return sum(list(cnt.values())) + odd_cnt
    • cnt.values()는 각 문자의 수정된 빈도 값들을 반환합니다.
    • 이 값들을 합산하여 팰린드롬의 최대 길이를 계산합니다.
    • 만약 odd_cnt가 1이라면, 이는 홀수 빈도를 가진 문자가 존재한다는 것을 의미하며, 그 문자를 팰린드롬의 중앙에 배치할 수 있으므로 길이에 1을 추가로 더합니다.

이 코드는 주어진 문자열에서 만들 수 있는 가장 긴 팰린드롬의 길이를 계산합니다. 문자열 내 각 문자의 빈도를 확인한 후, 홀수 빈도를 가진 문자의 빈도를 짝수로 변환하고, 홀수 빈도가 존재할 경우 추가로 중앙에 배치할 수 있는 문자를 고려해 최종 길이를 반환합니다. 이 과정에서 Counter를 활용하여 각 문자의 빈도를 계산하고, 이를 통해 최적의 팰린드롬 길이를 구하는 방식입니다.

시간 복잡도

  1. Counter 생성:

    cnt = Counter(s)
    • Counter(s)는 문자열 s를 한 번 순회하며 각 문자의 빈도를 계산합니다.
    • 문자열 s의 길이를 n이라고 하면, 이 부분의 시간 복잡도는 O(n)입니다.

  2. for 루프:

    for key, value in cnt.items():
    if value % 2 != 0:
        cnt[key] = value - 1
        odd_cnt = 1
    • cnt.items()는 각 문자의 빈도에 대해 순회합니다.
    • cnt의 최대 크기는 문자열에 포함된 고유 문자의 수입니다. 영어 대소문자만 포함된다고 가정하면 최대 52개의 문자가 될 수 있습니다. 따라서 이 루프의 복잡도는 O(1)에 가깝지만, 일반적으로는 O(k)로, 여기서 k는 고유 문자의 수입니다. 그러나 k는 상수로 간주되므로 시간 복잡도에 큰 영향을 주지 않습니다.
    • 따라서 이 루프에서의 시간 복잡도는 O(1)입니다.

  3. 합 계산 및 반환:

    return sum(list(cnt.values())) + odd_cnt
    • cnt.values()의 합을 계산하는 것은 최대 52개의 값을 합산하는 것입니다.
    • 따라서 이 단계의 시간 복잡도 역시 O(1)입니다.

최종 시간 복잡도

  • 가장 큰 영향을 미치는 부분은 Counter(s)를 만드는 부분이므로, 최종 시간 복잡도는 O(n)입니다.

공간 복잡도

  1. Counter 객체:
    • cnt = Counter(s)는 문자열의 문자를 세는 딕셔너리입니다.
    • 최악의 경우 모든 문자가 고유할 때, cnt는 최대 52개의 키-값 쌍을 가질 수 있습니다. 이는 상수로 간주될 수 있으므로, 이 부분의 공간 복잡도는 O(1)입니다.
  2. 추가 변수:
    • odd_cnt, key, value 등 추가 변수들은 상수 개수의 메모리만 차지하므로 공간 복잡도에 큰 영향을 미치지 않습니다.

최종 공간 복잡도

  • 최종적으로, 이 코드의 공간 복잡도는 O(1)입니다. 이는 입력 문자열의 길이에 상관없이 코드가 사용하는 추가 메모리가 일정하다는 것을 의미합니다.

결론

  • 시간 복잡도: O(n) (문자열의 길이 n에 비례)
  • 공간 복잡도: O(1) (입력 문자열의 길이와 무관한 상수 공간 사용)

결과

https://leetcode.com/problems/longest-palindrome/submissions/1370818515

4. 다른 풀이

다른 풀이로는 Counter 모듈을 사용하지 않고, 문자열의 문자들을 직접 카운트해서, 해시 테이블을 만드는 코드입니다. 또한, 홀수 개수를 처리하는 방법이 가장 보편적인 방법을 사용했습니다.

Python 코드 구현:

def longestPalindrome(sekf,s):
    # 각 문자의 빈도를 세기 위한 딕셔너리 생성
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1

    length = 0
    odd_found = False

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

    # 홀수 빈도의 문자가 있다면 중앙에 하나 배치
    if odd_found:
        length += 1

    return length

복잡도:

  • 시간 복잡도: O(n) (문자열을 한 번 훑어보면서 빈도를 계산하기 때문에, 문자열의 길이를 n이라고 할 때)
  • 공간 복잡도: O(1) (빈도 딕셔너리는 최대 52개의 키를 가지므로, 26개의 소문자와 26개의 대문자를 고려)

결과

https://leetcode.com/problems/longest-palindrome/submissions/1370819042

5. 이것이 왜 그리디지?

이 문제를 해결하는 방법이 그리디 알고리즘(Greedy Algorithm)으로 간주되는 이유는, 문제를 해결하는 과정에서 "각 단계에서 가장 좋은 선택을 하여 최종적으로 최적의 결과를 얻는다"는 그리디 알고리즘의 핵심 개념을 따르고 있기 때문입니다.

그리디 알고리즘의 특징:

  1. 매 순간 최적의 선택: 그리디 알고리즘은 문제의 각 단계에서 현재 상황에서 가장 좋다고 생각되는 선택을 합니다.
  2. 전역적 최적화로 이어짐: 각 단계에서의 최적 선택들이 모여 전체 문제의 최적 해를 보장합니다.
  3. 미래를 고려하지 않음: 현재 상황에서의 최적 선택만 고려하며, 다음에 어떤 일이 일어날지는 생각하지 않습니다.

이 문제에서 그리디 알고리즘이 적용되는 방식:

  1. 문자의 빈도 분석:
    • 각 문자에 대해, 현재 그 문자의 빈도만을 고려하여 결정을 내립니다.
    • 빈도가 짝수인 경우, 이 문자들을 모두 팰린드롬에 포함시키는 것이 최적의 선택입니다. (더 이상 사용할 수 없기 때문에 현재 최적 선택)
    • 빈도가 홀수인 경우, count - 1을 사용하여 가능한 많은 문자를 포함시키는 것이 최적의 선택입니다. (이 역시 현재 최적 선택)
  2. 결과적으로 최적의 팰린드롬 길이:
    • 위의 선택들을 통해 얻어진 결과는 최종적으로 만들 수 있는 가장 긴 팰린드롬의 길이가 됩니다.
    • 이 과정에서 현재 선택이 다음 선택에 영향을 미치지 않기 때문에, 각 단계에서의 최적 선택이 전체 최적 해를 보장하게 됩니다.

요약:

이 알고리즘이 그리디 알고리즘인 이유는, 각 문자에 대해 별도로 빈도를 고려하고 그 빈도에 따라 최선의 선택을 즉각적으로 내리는 방식으로 문제를 해결하기 때문입니다. 이 과정에서 나중에 더 나은 선택이 있을 수 있다는 가능성에 대한 고민 없이, 항상 현재 상황에서 가장 좋은 선택을 합니다. 이렇게 해서 전체적으로 최적의 해를 도출하게 됩니다.

마무리

오늘 문제는 문자열이 주어졌을때, 주어진 문자열을 활용해서 만들 수 있는 펠린드롬 문자열 중 가장 큰 길이를 리턴하는 문제였습니다.

펠린드롬 문자열을 어떻게 다루고, 해시 테이블을 형성하는지를 학습할 수 있는 문제였습니다.

두 가지 방법으로 코드를 작성했는데, 사실상 크게 다르지 않았습니다. 다만, Counter 모듈이 기억나지 않을때, 두번째 방법처럼 직접 해시 테이블을 작성할 수 있습니다.

전체 코드와 테스트 케이스 평가 및 시간 측정을 진행한 코드는 저의 깃허브에서 확인하실 수 있습니다.

읽어주셔서 감사합니다!

profile
말하는 감자
할 수 있다
이전 포스트

99클럽 코테 스터디 37일차 TIL (수학적 호기심) - 백준

다음 포스트

99클럽 코테 스터디 39일차 TIL (Assign Cookies) - LeetCode

post-custom-banner

0개의 댓글