[99클럽 코테 스터디] 38일차 TIL - Longest Palindrome

오늘의 학습 키워드

</> 탐욕법

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int longestPalindrome(String s) {
        String[] list = s.split("");
        Map<String, Integer> countList = new HashMap<>();
        int result = 0;
        boolean odd = false;
        for(int i = 0; i < list.length; i++){
            countList.put(list[i], countList.getOrDefault(list[i], 0) + 1);
        }
        for(int p : countList.values()){
            if(p % 2 == 0){
                result += p;
            } else {
                result += p - 1;
                odd = true;
            }
        }
         if(odd){
                result++;
            }
        return result;
        
    }
}

오늘의 회고

오늘 문제는 주어진 문자열 s를 이용해 Palindrome 즉, 똑바로 읽으나 거꾸로 읽으나 똑같은 회문을 만들고 만들수 있는 문자열의 최대길이를 구해 반환하는 문제이다.

우선 문자열을 split()을 이용해 각각 문자로 나눠주었다

String[] list = s.split("");

그리고 문자의 개수를 세어주어야 했기 때문에 getOrDefault를 사용하기로 했고 그 값을 담아주기 위한 Map을 만들어주었다.

Map<String, Integer> countList = new HashMap<>();

그리고 만들어둔 문자 배열을 탐색하며 해당 값이 있으면 해당 문자가 있으면 저장 개수를 반환하고 거기 +1을 해주어 출현빈도를 완성해준다.

for(int i = 0; i < list.length; i++){
	countList.put(list[i], countList.getOrDefault(list[i],0) + 1)
}

여기까지 완성 되었다면 조건에 맞춰서 회문을 만들어주면 된다.
내 조건은 짝수일 경우에는 해당 값의 출현빈도만큼 추가해주고 홀수일 경우 그 값의 -1, 그리고 홀수가 여러개일 경우에도 1개의 글자는 중앙으로 배치해 사용할 수 있으므로 홀수 값이 존재할 경우에 +1를 해주게 만들었다.

for(int p : countList.values()){
	if(p % 2 == 0){
		result += p;
	} else {
		result += p - 1;
		odd = true;
	}
}
if(odd){
	result++;
}

이제 모두 완성되었으니 result를 반환해주도록 한다.

return result;

AI 코드리뷰

현재 코드의 장점

1. HashMap을 사용하여 문자 빈도를 효율적으로 계산합니다.
2. 팰린드롬의 특성(짝수 개수의 문자와 최대 1개의 홀수 개수 문자)을 잘 활용하고 있습니다.

현재 코드의 단점

1. String을 배열로 변환하는 과정(s.split(""))이 불필요합니다.
2. 변수명 p가 의미를 명확히 전달하지 않습니다.

시간 복잡도

• O(n), 여기서 n은 문자열 s의 길이입니다.

개선된 코드 제안

class Solution {
    public int longestPalindrome(String s) {
        int[] charCount = new int[128];  // ASCII 문자 수
        int result = 0;
        boolean hasOdd = false;

        for (char c : s.toCharArray()) {
            charCount[c]++;
        }

        for (int count : charCount) {
            result += count / 2 * 2;
            if (count % 2 == 1) {
                hasOdd = true;
            }
        }

        return hasOdd ? result + 1 : result;
    }
}

현재 코드의 장점

1. char 배열을 직접 사용하여 String 분할 과정을 제거했습니다.
2. ASCII 문자만 고려하는 int 배열을 사용하여 HashMap 대신 더 효율적인 메모리 사용이 가능합니다.
3. 변수명을 더 명확하게 변경했습니다 (예: p -> count, odd -> hasOdd).
4. 짝수 개수 계산을 count / 2 * 2로 단순화했습니다.

현재 코드의 단점

1. ASCII 문자만 처리할 수 있어, 유니코드 문자열에는 적합하지 않을 수 있습니다.

시간 복잡도

• 시간 복잡도: O(n), 여기서 n은 문자열 s의 길이입니다.
• 공간 복잡도: O(1), 고정 크기의 배열을 사용하므로 입력 크기와 무관합니다.

두 버전 모두 시간 복잡도는 O(n)이지만, 개선된 버전이 상수 시간에서 더 효율적입니다. 또한, 개선된 버전은 공간 복잡도가 O(1)로, 원래 버전의 O(n)보다 우수합니다.

이 솔루션은 대부분의 경우에 더 효율적이지만, 유니코드 문자열을 처리해야 하는 경우에는 원래의 HashMap 기반 솔루션이 더 적합할 수 있습니다.

---

내일 공부할 것 :

아스키코드는 생각 못해봤는데 다시 보면서 이해를 해봐야겠다.

문제

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