C++로 만들 수 있는 가장 긴 회문(Palindrome)의 길이 구하기

문제 개요

소문자 또는 대문자로만 이루어진 문자열이 주어졌을 때, 이 문자들을 조합하여 만들 수 있는 가장 긴 회문(palindrome)의 길이를 찾아야 합니다.

단, 문자열은 대소문자를 엄격하게 구분하므로 "Aa"는 회문으로 인정되지 않습니다.

예를 들어 입력이 "abccccdd"라면, 만들 수 있는 가장 긴 회문 중 하나는 "dccaccd"이며 그 길이는 7입니다. 따라서 출력값은 7이 됩니다.

해결 접근 방법

회문의 핵심 성질을 활용하면 문제를 쉽게 해결할 수 있습니다.

• 각 문자의 등장 횟수를 먼저 계산합니다.
• 짝수 개로 등장하는 문자들은 회문 양쪽에 모두 배치할 수 있습니다.
• 홀수 개로 등장하는 문자들도 (개수 − 1)만큼은 사용할 수 있으며, 딱 하나의 홀수 문자는 회문의 정중앙에 배치될 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

1. 문자별 개수를 저장할 맵(mp)을 하나 정의합니다.
2. 문자열 s의 각 문자 i에 대해 mp[i]의 값을 1씩 증가시킵니다.
3. ma := 0, c := 0, ans := 0으로 초기화합니다.
4. mp의 각 키-값 쌍 i에 대해 다음을 수행합니다.
   • 값을 2로 나눈 나머지가 1(즉, 홀수)이라면 ma를 1 증가시킵니다.
   • c에 해당 문자의 개수를 더합니다.
5. ma가 0보다 크다면 ma를 1 감소시킵니다. (정중앙에 배치할 수 있는 문자 하나를 허용)
6. ans := c − ma를 계산합니다.
7. ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestPalindrome(string s) {
      unordered_map<char, int> mp;
      for (auto i : s)
         mp[i]++;
      int ma = 0, c = 0, ans = 0;
      for (auto i : mp) {
         if ((i.second) % 2 == 1)
            ma++;
         c += i.second;
      }
      if (ma > 0)
         ma--;
      ans = c - ma;
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.longestPalindrome("abccccdd"));
}

입력

"abccccdd"

출력

7

복잡도 분석

• 시간 복잡도: O(n) — 문자열을 한 번 순회하며 빈도를 세고, 맵을 한 번 순회하며 결과를 계산합니다.
• 공간 복잡도: O(1) — 영문자는 최대 52종(대소문자 합계)으로 제한되므로 맵의 크기는 일정합니다.