이 문제에서는 카멜케이스(camelCase)로 작성된 문자열 배열과 하나의 패턴이 주어지며, 주어진 패턴과 일치하는 문자열을 모두 찾아 출력해야 합니다.
핵심 개념 정리
문자열 배열(String Array)은 요소가 모두 문자열(string) 타입인 배열을 의미합니다.
카멜케이스(CamelCase)는 프로그래밍에서 가장 널리 사용되는 명명 규칙 중 하나로, 새로운 단어의 첫 글자는 대문자로 시작하고 나머지 글자는 모두 소문자로 표기하는 방식입니다.
예시: iLoveProgramming
문제 정의
목표는 주어진 패턴과 일치하는 모든 문자열을 찾는 것입니다.
입력 : "TutorialsPoint" , "ProgrammersPoint" , "ProgrammingLover" , "Tutorials" 패턴 : 'P' 출력 : "TutorialsPoint" , "ProgrammersPoint" , "ProgrammingLover"
설명: 대문자 'P'를 포함하는, 즉 대문자 시퀀스가 'P'로 시작하는 모든 문자열을 선택했습니다.
접근 방법: 트라이(Trie) 활용
이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 트라이는 문자열 검색에 최적화된 트리 구조로, 다음 순서로 진행됩니다.
- 사전의 각 단어에서 대문자만 추출하여 트라이에 삽입합니다. 이때 원본 단어 전체를 해당 노드에 함께 저장합니다.
- 주어진 패턴의 대문자를 따라 트라이를 탐색합니다.
- 탐색이 완료된 노드에 저장된 모든 단어를 출력합니다. 이 단어들이 바로 패턴과 일치하는 문자열입니다.
소문자는 삽입 과정에서 건너뛰어지므로, 패턴 매칭은 오직 대문자 시퀀스를 기준으로 수행됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
TreeNode* children[26];
bool isLeaf;
list<string> word;
};
TreeNode* getNewTreeNode(void){
TreeNode* pNode = new TreeNode;
if (pNode){
pNode->isLeaf = false;
for (int i = 0; i < 26; i++)
pNode->children[i] = NULL;
}
return pNode;
}
void insert(TreeNode* root, string word){
int index;
TreeNode* pCrawl = root;
for (int level = 0; level < word.length(); level++){
if (islower(word[level]))
continue;
index = int(word[level]) - 'A';
if (!pCrawl->children[index])
pCrawl->children[index] = getNewTreeNode();
pCrawl = pCrawl->children[index];
}
pCrawl->isLeaf = true;
(pCrawl->word).push_back(word);
}
void printAllWords(TreeNode* root){
if (root->isLeaf){
for(string str : root->word)
cout << str << endl;
}
for (int i = 0; i < 26; i++){
TreeNode* child = root->children[i];
if (child)
printAllWords(child);
}
}
bool search(TreeNode* root, string pattern){
int index;
TreeNode* pCrawl = root;
for (int level = 0; level <pattern.length(); level++) {
index = int(pattern[level]) - 'A';
if (!pCrawl->children[index])
return false;
pCrawl = pCrawl->children[index];
}
printAllWords(pCrawl);
return true;
}
void findAllMatch(vector<string> dictionary, string pattern){
TreeNode* root = getNewTreeNode();
for (string word : dictionary)
insert(root, word);
if (!search(root, pattern))
cout << "No match found";
}
int main(){
vector<string> dictionary = { "Tutorial" , "TP" , "TutorialsPoint" , "LearnersPoint", "TutorialsPointsPrograming" , "programmingTutorial"};
string pattern = "TP";
findAllMatch(dictionary, pattern);
return 0;
}
실행 결과
TP TutorialsPoint TutorialsPointsPrograming
코드 동작 원리
- insert(): 단어를 한 글자씩 확인하며 소문자는 건너뛰고 대문자만 트라이의 경로로 사용합니다. 단어의 끝에 도달하면 해당 노드를 리프로 표시하고 원본 단어를 리스트에 추가합니다.
- search(): 패턴의 각 대문자를 따라 트라이를 내려갑니다. 중간에 경로가 존재하지 않으면 false를 반환하여 "No match found"를 출력합니다.
- printAllWords(): 패턴 탐색이 종료된 노드부터 재귀적으로 하위 트리를 순회하며 저장된 모든 단어를 출력합니다.
예제에서 패턴 "TP"는 대문자 시퀀스가 T 다음 P로 이어지는 단어들, 즉 "TP", "TutorialsPoint", "TutorialsPointsPrograming"과 일치함을 확인할 수 있습니다. 삽입과 탐색 연산은 각각 단어 및 패턴의 길이에 비례하여 수행되므로, 전체 시간 복잡도는 O(모든 단어의 총 길이 + 패턴 길이)로 매우 효율적입니다.