문제

팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, 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을 출력한다.

접근 과정

특정 문자열이 팰린드롬인지 판별하기 위한 함수 isPelindrome()을 작성하였다.
처음엔 로직을 잘못 작성하면 시간초과가 날만한 문제라 생각했는데 합이 입력 단위가 생각보다 작았다. 최적화는 생각하지 않고 무작정 모든 경우의 수를 검사해도 시간이 충분하므로 입력받은 모든 단어들의 하나하나 조합하고 팰린드롬인지 검사하는 방식으로 구현하였다.
본 문제에서는 큰 영향이 없지만 std::string 이나 std::vector 등의 클래스의 최대 길이가 정해져 있는 경우라면 reserve() 메소드를 호출하여 약간의 성능 이득을 취할 수 있다. reserve() 메소드는 자료구조 내부의 동적 메모리 공간을 미리 확보해두는 메소드로 길이가 증가함에 따라 발생하는 추가적인 메모리 동적할당을 막을 수 있다. 본 문제에서는 고작 4ms 빨라졌다 ㅋㅋ

소스 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool isPelindrome(const string& s) {
    unsigned int half = s.length() / 2;
    for (unsigned int i = 0; i < half; ++i) {
        if (s[i] != s[s.length() - i - 1]) { return false; }
    }
    return true;
}

int main() {
    int T, k;
    vector<string> words;
    string s;
    words.reserve(101);
    s.reserve(10010);

    cin >> T;
    for (int i = 0; i < T; ++i) {
        cin >> k;
        
        words.resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> words[j];
        }

        bool bFind = false;
        for (unsigned int a = 0; a < words.size() && !bFind; ++a) {
            for (unsigned int b = 0; b < words.size(); ++b) {
                if (a == b) { continue; }
                s = words[a] + words[b];
                if (isPelindrome(s)) {
                    bFind = true;
                    break;
                }
            }
        }

        if (bFind) { cout << s << '\n'; }
        else { cout << 0 << '\n'; }
        words.clear();
    }
    return 0;
}