[Leetcode] 409. Longest Palindrome

문제

나의 풀이

첫 시도

'개수가 홀수인 것 중 가장 큰 것을 palindrome에 포함시킨다'라는 로직으로 구현하여서, 주어진 테스트 코드들은 전부 통과했지만 제출하고 나니 실패.
-> 간과한 것은 홀수만큼 존재하는 문자여도 짝수만큼만 palindrome에 추가할 수 있다는 조금 당연한 사실이었다.
홀수만큼 존재하는 문자들도 -1하여 palindrome 길이에 추가하고, 이후 홀수가 존재했을 시 길이에 1을 추가하도록 구현하니 통과했다.

import java.util.HashMap;

class Solution {
    public int longestPalindrome(String s) {
        HashMap<Character,Integer> chars = new HashMap<>();
        boolean checkOdd=false;
        int answer = 0;
        for(char c : s.toCharArray()) {
            chars.put(c, chars.getOrDefault(c, 0)+1);
        }

        for(char c : chars.keySet()) {
            int curCnt = chars.get(c); 
            if(curCnt%2 ==0) {
                answer += curCnt; 
            } else {
                answer += curCnt-1;
                if(!checkOdd) checkOdd = true;
            }
        }

        if(checkOdd) answer+=1;
        return answer;
    }
}

다른 풀이

public int longestPalindrome(String s) {
        if(s==null || s.length()==0) return 0;
        HashSet<Character> hs = new HashSet<Character>();
        int count = 0;
        for(int i=0; i<s.length(); i++){
            if(hs.contains(s.charAt(i))){
                hs.remove(s.charAt(i));
                count++;
            }else{
                hs.add(s.charAt(i));
            }
        }
        if(!hs.isEmpty()) return count*2+1;
        return count*2;
}

나는 map을 사용하여 구현했는데, 사실 palindrome의 많은 문제들은 set을 사용해서 구현 가능한 듯하고 성능도 더 좋은 것 같다.

• 짝수만큼 존재할 때 바로 길이에 포함시켜주는 방식으로 for문을 한 번만 실행하여 시간복잡도가 내 코드보다 훨씬 좋다.
• 추가 변수 없이 set이 비어있지 않을 경우 odd가 존재했음을 알아낼 수 있다.

후기

palindrome에 대한 이해 부족으로 인해 단번에 정답을 맞추지 못했던 문제인 것 같다.
palindrome 관련 문제가 나오면 자료구조로 map 대신 set을 활용하여 시간복잡도를 줄이는 방법을 먼저 생각해보아야겠다.