백준 8892 팰린드롬 - C++

https://www.acmicpc.net/problem/8892

8892번: 팰린드롬

<문제>

 

팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다.

상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC 문제가 저장되어 있는 서버에 접속할 수 있는 비밀번호에 대한 힌트이다. 비밀번호는 k개의 단어 중에서 두 단어를 합쳐야 되고, 팰린드롬이어야 한다. 예를 들어, 단어가 aaba, ba, ababa, bbaa, baaba일 때, ababa와 ba를 합치면 팰린드롬 abababa를 찾을 수 있다.

단어 k개 주어졌을 때, 팰린드롬을 찾는 프로그램을 작성하시오.

 

<입력>

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 공책에 적혀져있는 단어의 수 k(1 ≤ k ≤ 100)가 주어진다. 다음 k개 줄에는 a부터 z까지 알파벳으로 이루어진 단어가 한 줄에 하나씩 주어진다. 모든 단어 길이의 합은 10,000보다 작거나 같다.

 

<출력>

 

각 테스트 케이스마다 팰린드롬을 출력한다. 만약, 가능한 팰린드롬이 여러 가지라면 아무거나 출력한다. 팰린드롬을 만들 수 없는 경우에는 0을 출력한다.

 

<Tip>

 

문자열 A, B에 대해서 A+B를 검사했으면 당연히 B+A도 확인하자.

모든 단어의 길이의 합이 최대 10,000이기 때문에 제한시간 1초내에도 n^2 알고리즘을 적용할 수 있다.

Brute Force 접근 방식 역시 가능하다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int t, n;

void solve(vector<string> v) {

	int len, i, j, k;
	string tmp, tmp2;

	for (i = 0; i < n-1; i++) {
		for (j = i + 1; j < n; j++) {
			// v[i] 와 v[j]를 비교
			tmp = v[i]; tmp2 = v[j];
			tmp += v[j]; tmp2 += v[i];
			len = tmp.size();

			for (k = 0; k < len / 2; k++) {
				if (tmp[k] != tmp[len - 1 - k]) {
					break;
				}
			}
			if (k == len / 2) {
				cout <<tmp <<"\n";
				return;
			}

			for (k = 0; k < len / 2; k++) {
				if (tmp2[k] != tmp2[len - 1 - k]) {
					break;
				}
			}
			if (k == len / 2) {
				cout << tmp2 <<"\n";
				return;
			}

		}
	}
	printf("0\n");
}

int main(void) {

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		vector<string> v;
		scanf("%d", &n);
		getchar();
		for (int j = 0; j < n; j++) {
			string s;
			getline(cin, s);
			//getchar();
			v.push_back(s);
		}
		solve(v);
	}

	return 0;
}