99클럽 코테 스터디 38일차 TIL | Longest Palindrome

🖥️ 문제

📝 풀이

import java.util.HashMap;

public class Main {
    public static int longestPalindrome(String s) {
        int oddCount = 0;
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        
        for (char ch : s.toCharArray()) {
            int freq = frequencyMap.getOrDefault(ch, 0) + 1;
            frequencyMap.put(ch, freq);
            
            if (freq % 2 == 0) 
                oddCount--;
            else 
                oddCount++;
        }
        
        return s.length() - (oddCount > 0 ? oddCount - 1 : 0);
    }
}

먼저, 각 문자의 빈도를 추적하기 위해 HashMap을 사용했다. 이 맵은 문자열을 한 번 순회하며 각 문자가 몇 번 등장하는지를 기록한다. 이렇게 하면 각 문자가 짝수 번 등장하는지, 홀수 번 등장하는지를 쉽게 알 수 있다.

빈도가 짝수인 문자는 회문에서 양쪽 대칭에 균등하게 배치될 수 있다. 하지만 빈도가 홀수인 문자는 중앙에 하나만 위치할 수 있다. 따라서, 홀수 번 등장하는 문자 중 하나는 중앙에 위치하고 나머지는 짝수로 만들기 위해 한 번을 제외하고 모두 대칭에 배치한다. 이 원리를 적용하여 회문을 만들었다.

oddCount라는 변수를 사용하여 홀수 빈도의 문자가 몇 개 있는지를 찾고, 문자열을 순회하면서 각 문자의 빈도가 짝수로 변할 때마다 oddCount를 감소시킨다. (홀수로 변할 때마다 증가) 이후 최종 회문의 길이는 전체 문자열 길이에서 oddCount - 1을 뺀 값이 된다.

왜냐하면, 홀수 빈도를 가진 문자들 중 하나는 중앙에 위치할 수 있기 때문이다. 만약 모든 문자가 짝수 빈도를 가지면, 문자열 전체가 회문이 될 수 있다.