swea 19003 팰린드롬 문제

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

1. M 길이를 가지는 N개의 문자열 주어짐
2. 문자열 몇개를 골라서 적당히 재배열하여 (문자열 자체 재배열 불가) 가장 긴 팰린드롬 구하기

팰린드롬
역순으로 읽어도 같은 문자열

for(int i=0;i<str.length()/2;i++){
	if( str[i] != str[len-1-i]){
		return 0;
    }
}
return 1;

해석

같은 길이의 문자열을 조합해서 팰린드롬이 만들어진다면

1. 대칭인 문자열끼리 짝수개로 조합
   ex) 같은 숫자가 대칭인 문자열이라면..
   1 2 3 3 2 1 와 같음
2. 대칭인 문자열과 가운데 스스로 팰린드롬인 문자열 총 홀수개로 구성
   ex) 1 2 3 (팰린드롬 문자열) 3 2 1 와 같음

-> set을 활용해서 reverse한 문자열이 존재한다면 최종 팰린드롬 가능 문자열로 더한다
-> 마지막에 남은 문자열 중 스스로 팰린드롬인 문자열이 있다면 최종 팰린드롬 가능 문자열로 더한다

=> ( 대칭인 문자열 수 + ( 스스로 팰린드롬인 수 있다면 +1) ) * M

코드

#include <stdio.h>
#include <vector> 
#include <iostream>
#include <set>
#include <string>
#include <algorithm>

// 1. 각각 팰린드롬인지 확인
// 2. 팰린드롬 아닌거 짝 있는지 확인
// 짝 있는 애들 + 가운데 대칭 넣을 수 있는지 (+1) 
using namespace std;
int N, M;
int check(string s){
	for(int i=0;i<M/2;i++){
		if(s[i] != s[M-1-i]){
			return 0;
		}
	}
	return 1;
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	scanf("%d",&T);
	string tmp,tmp2;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		scanf("%d %d",&N,&M);
		set<string> s;
		int match_cnt = 0;
		for(int i=0;i<N;i++){
			
			cin >> tmp;
			tmp2 = tmp;
			reverse(tmp2.begin(), tmp2.end());
			if(s.find(tmp2) != s.end()){ // 존재함  
				match_cnt += 2;
				s.erase(tmp2); // 지우기  
			}else{
				s.insert(tmp);
			}
		
		}
		
		for(auto iter = s.begin() ; iter != s.end();iter++){
			if(check(*iter)){
				match_cnt ++;
				break;
			}
		}
		printf("#%d %d\n",test_case, match_cnt * M);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}