Longest Palindrome

✏️오늘의 문제

💡회문 계산하기

1. 문자 빈도 계산

HashMap<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) {
    charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}

• 목적: 문자열 내 각 문자의 빈도를 세기 위해 HashMap을 사용합니다.
• 작동 방식:
  • s.toCharArray()를 통해 문자열 s를 문자 배열로 변환합니다.
  • 각 문자를 순회하면서 charCount 맵에 문자의 개수를 저장합니다.
  • getOrDefault(c, 0)는 문자가 이미 맵에 존재하면 그 값을 반환하고, 존재하지 않으면 0을 반환합니다. 이 값을 1 더하여 해당 문자의 빈도를 업데이트합니다.

예시: 문자열 "abccccdd"의 경우:

• 'a'는 1회, 'b'는 1회, 'c'는 4회, 'd'는 2회 등장하므로, 최종적으로 charCount는 {'a': 1, 'b': 1, 'c': 4, 'd': 2}가 됩니다.

2. 짝수와 홀수의 개수 확인

int cnt = 0;
boolean hasOdd = false;
for (int count : charCount.values()) {
    if (count % 2 == 0) {
        cnt += count; // 짝수는 그대로 더함
    } else {
        cnt += count - 1; // 홀수는 1을 뺀 값을 더함
        hasOdd = true; // 홀수가 있음을 기록
    }
}

• 목적: 각 문자의 빈도를 확인하여 짝수와 홀수의 개수를 구분합니다.
• 작동 방식:
  • cnt는 팰린드롬을 구성할 수 있는 문자들의 총 개수를 저장합니다.
  • charCount.values()를 통해 각 문자의 빈도를 순회합니다.
  • 빈도가 짝수인 경우, 해당 빈도를 cnt에 그대로 더합니다. 이는 짝수 개수의 문자가 대칭적으로 배치될 수 있기 때문입니다.
  • 빈도가 홀수인 경우, 1을 뺀 값을 cnt에 더합니다. 이는 홀수 개수의 문자는 대칭적으로 배치할 수 없고, 중앙에 하나만 배치할 수 있기 때문입니다. 또한, 홀수가 발견되면 hasOdd를 true로 설정하여 홀수 문자가 존재함을 기록합니다.

예시: 위의 예시에서:

• 'c'는 4회(짝수), 'd'는 2회(짝수), 'a'는 1회(홀수), 'b'는 1회(홀수)입니다.
• 따라서 cnt는 4 + 2 + (1 - 1) + (1 - 1) = 6이 됩니다. 이때 hasOdd는 true가 됩니다.

3. 결과 계산

if (hasOdd) {
    cnt += 1; // 홀수가 있으면 중앙에 하나 추가 가능
}
return cnt;

• 목적: 최종적으로 팰린드롬의 길이를 계산합니다.
• 작동 방식:
  • 만약 hasOdd가 true라면, 중앙에 홀수 개수의 문자를 하나 추가할 수 있으므로 cnt에 1을 더합니다.
  • 최종적으로 cnt를 반환하여 가장 긴 팰린드롬의 길이를 제공합니다.

예시: 위의 예시에서:

• cnt는 6이고, hasOdd가 true이므로 1을 더하여 최종 결과는 7이 됩니다. 이는 "dccaccd"와 같은 팰린드롬을 형성할 수 있습니다.

전체 알고리즘의 시간 복잡도

• 이 알고리즘은 O(n) 시간 복잡도를 가집니다. 여기서 n은 문자열의 길이입니다. 각 문자를 한 번씩만 순회하므로 효율적입니다.
• 공간 복잡도는 O(1)입니다. 이는 최대 26개의 알파벳 문자만을 고려하기 때문입니다.

결론

이 알고리즘은 주어진 문자열에서 가장 긴 팰린드롬을 구성할 수 있는 문자의 개수를 효율적으로 계산합니다. 문자 빈도를 기반으로 하여 짝수와 홀수의 개수를 구분하고, 중앙에 홀수 문자를 추가할 수 있는지를 판단하여 최종 결과를 도출합니다. 이 방법은 다양한 문자열에 대해 빠르게 결과를 도출할 수 있는 강력한 접근 방식입니다.