"Madam"이나 "racecar"처럼 거꾸로 읽어도 앞에서 읽은 것과 똑같은 단어를 회문(palindrome)이라고 부릅니다.
문자열들의 집합 또는 리스트가 주어졌을 때, 리스트 안의 어떤 두 문자열을 서로 연결했을 때 회문을 만들 수 있는지 확인하는 C++ 코드를 작성해야 합니다. 그런 쌍이 존재하면 "Yes"를, 존재하지 않으면 "No"를 출력하면 됩니다.
이 튜토리얼에서는 입력으로 문자열 배열이 주어지고, 그에 따라 문자열 값이 출력됩니다.
입력 예시
list[] = {"flat", "tea", "chair", "ptalf", "tea"}출력
Yes
"flat"과 "ptalf"라는 쌍이 존재하며, 이 둘을 연결한 "flatptalf"가 회문이 됩니다.
또 다른 예시
list[] = {"raman", "ram", "na", "ar", "man"}출력
Yes
"na"와 "man"이라는 쌍이 존재하며, 이 둘을 연결한 "naman"이 회문이 됩니다.
해결 방법 1: 브루트 포스(Brute Force) 접근법
배열의 각 문자열에 대해 나머지 모든 문자열과 조합했을 때 회문이 되는지 하나씩 확인합니다. 회문이 되는 쌍을 발견하면 true를 반환하고, 배열의 모든 요소를 탐색했음에도 적절한 쌍을 찾지 못하면 false를 반환합니다.
- 시간 복잡도: O(N²)
- 공간 복잡도: O(1)
브루트 포스 구현 예제
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome (string str) {
int len = str.length ();
for (int i = 0; i < len / 2; i++)
if (str[i] != str[len - i - 1])
return false;
return true;
}
bool checkPalindromePair (vector < string > vect) {
for (int i = 0; i < vect.size () - 1; i++) {
for (int j = i + 1; j < vect.size (); j++) {
string check_str = "";
check_str = check_str + vect[i] + vect[j];
if (isPalindrome (check_str))
return true;
}
}
return false;
}
int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
}실행 결과
Yes
해결 방법 2: 트라이(Trie) 자료구조를 활용한 최적화 접근법
이 문제는 트라이(Trie) 자료구조를 사용하면 더 효율적으로 해결할 수 있습니다.
먼저 빈 트라이를 생성하고, 배열의 각 문자열에 대해 현재 단어의 역순(reversed)을 트라이에 삽입하면서 어느 인덱스까지가 회문인지 함께 저장합니다. 그다음 배열을 다시 순회하면서 각 문자열마다 아래 작업을 수행합니다.
- 해당 문자열이 트라이에 완전히 존재하면 true를 반환합니다.
- 부분적으로만 존재한다면 — 남은 부분이 회문인지 확인하고, 회문이라면 true를 반환합니다. 이는 해당 쌍이 회문을 형성한다는 의미입니다.
- 시간 복잡도: O(Nk²)
- 공간 복잡도: O(N)
여기서 N은 리스트에 있는 단어의 개수이고, k는 회문 검사 시 확인되는 최대 길이입니다.
트라이 기반 구현 예제
#include<bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
vector < int >pos;
int id;
bool isLeaf;
};
struct TrieNode *
getNode (void) {
struct TrieNode *pNode = new TrieNode;
pNode->isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
bool isPalindrome (string str, int i, int len) {
while (i < len) {
if (str[i] != str[len])
return false;
i++, len--;
}
return true;
}
void insert (struct TrieNode *root, string key, int id) {
struct TrieNode *pCrawl = root;
for (int level = key.length () - 1; level >= 0; level--) {
int index = CHAR_TO_INDEX (key[level]);
if (!pCrawl->children[index])
pCrawl->children[index] = getNode ();
if (isPalindrome (key, 0, level))
(pCrawl->pos).push_back (id);
pCrawl = pCrawl->children[index];
}
pCrawl->id = id; pCrawl->pos.push_back (id);
pCrawl->isLeaf = true;
}
void
search (struct TrieNode *root, string key, int id,
vector < vector < int > >&result) {
struct TrieNode *pCrawl = root;
for (int level = 0; level < key.length (); level++) {
int index = CHAR_TO_INDEX (key[level]);
if (pCrawl->id >= 0 && pCrawl->id != id && isPalindrome (key, level, key.size () - 1)) result.push_back ( { id, pCrawl->id} );
if (!pCrawl->children[index]) return; pCrawl = pCrawl->children[index];
}
for (int i:pCrawl->pos) {
if (i == id) continue;
result.push_back ( { id, i} );
}
}
bool checkPalindromePair (vector < string > vect) {
struct TrieNode *root = getNode ();
for (int i = 0; i < vect.size (); i++)
insert (root, vect[i], i);
vector < vector < int >>result;
for (int i = 0; i < vect.size (); i++) {
search (root, vect[i], i, result);
if (result.size () > 0) return true;
}
return false;
}
// 드라이버 코드
int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
}실행 결과
Yes
마무리
이 튜토리얼에서는 문자열 배열에서 회문 쌍을 찾는 두 가지 방법(브루트 포스와 최적화된 트라이 접근법)을 살펴보았습니다. 동일한 로직은 Java, Python 등 다른 프로그래밍 언어로도 구현할 수 있습니다. 첫 번째 방법은 주어진 모든 요소를 순회하며 해답을 찾는 기본적인 방식이고, 반면 두 번째 방법은 트라이 자료구조를 활용하여 거의 선형에 가까운 시간 복잡도로 답을 도출합니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.