R620(Div.2) B.Longest Palindrome

 

주어지는 문자열들을 통해 만들수 있는 가장 긴 팰린드롬의 길이와 팰린드롬을 출력한다!

나는 map과 set을 이용해서 풀었다

먼저 set에 담는데 뒤집어서 같은 문자열이 있다며 팰린드롬의 짝이 된다

그래서 만약 뒤집어서 있다면 뒤집은 문자열의 카운트만 증가시켜주고

없다면 set에 넣어준다

 

그리고 set을 돌아보면서 각 문자열의 /2만큼은 기본적으로 붙일 수 있으므로 답에 추가하자!

그리고 만약 개수가 1인것중에 팰린드롬인것이 있다면 그것을 답의 중간에 붙여주자!

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<string,int> mp;
set<string>s;
int n,m;
 
string ans,one;
 
int main(){
   scanf(" %d %d",&n,&m);
   for(int i=0;i<n;i++){
      string str; cin>>str;
      string rev = str;
      reverse(rev.begin(),rev.end());
      if(!s.count(rev)) {
         s.insert(str);
         mp[str]++;
      } else{
         mp[rev]++;
      }
   }
   
  for( auto it = s.begin(); it != s.end(); it++){
     string now = *it;
     int cnt = mp[now]/2;
     while(cnt--) ans+=now;
     if(mp[now]%2==1 && one==""){
        int sz = now.size()-1;
        bool c = true;
        for(int i=0;i<sz;i++){
           if(now[i]!=now[sz-i]) c=false;
        }
        if(c) one =now;
     }
  }
  int len = ans.size()*2+one.size();
  printf("%d\n",len);
  cout<<ans<<one;
  reverse(ans.begin(),ans.end());
  cout<<ans<<"\n";
}