[SWEA 19003] 팰린드롬 문제 [C/C++]

문제

SW Expert Academy

---

풀이

길이가 M인 서로 다른 문자열 N개가 주어졌을 때, 문자열을 결합하여 만들 수 있는 최장길이의 팰린드롬 문자열의 길이를 구하는 문제다. N, M이 각각 최대 100, 50으로 매우작아 N^2 방식으로 풀이해도 충분하다.

 

N개의 문자열에 대해 중복되는 문자열은 없다. 따라서 팰린드롬 문자열이 만약 존재한다면 한 번만 사용 가능하다.

펠린드롬 문자열이 아닌 경우에만 벡터에 담아주자.

 

벡터에 담은 문자열의 갯수가 N보다 작다면, 펠린드롬 문자열이 최소 1개이상 존재한다. 따라서 위에서 언급했듯 최장 팰린드롬 문자열을 만들 때 사용하기 위해 한 번만 사용해주자.

 

벡터에 있는 문자열들에 대해 팰린드롬 쌍을 이루는 문자열을 찾아주자.

탐색 대상 문자열에 대해 역전된 문자열이 벡터에 존재한다면 팰린드롬 쌍을 이룰 수 있다. 

탐색 대상의 중복 탐색을 방지하기 위해 벡터에서 제외해야한다. 때문에 만약 팰린드롬 쌍을 찾았다면 벡터에 남은 문자열은 짝을 찾지 못할 것이다. 갯수를 2만큼 증가시켜 주자.

 

갯수만큼 문자열의 길이( M )를 곱한 전체 길이를 출력하면 된다.

---

문제오류

주어진 예제 입력의 TC가 2로 오타가 있다. 예제의 TC는 4개이다.

---

소스코드

보기