카멜케이스 매칭(Camelcase Matching)은 문자열 처리 능력을 키울 수 있는 대표적인 알고리즘 문제입니다. 쿼리 문자열 목록과 하나의 패턴이 주어졌을 때, 각 쿼리가 패턴과 일치하는지 여부를 불리언(Boolean) 리스트로 반환해야 합니다. 즉, answer[i]는 queries[i]가 패턴과 일치하는 경우에만 true가 됩니다.
여기서 말하는 '일치'의 조건은 다음과 같습니다. 패턴 단어에 임의의 소문자들을 삽입했을 때 해당 쿼리 단어와 완전히 같아질 수 있다면 두 단어는 일치하는 것으로 간주합니다. 대소문자의 순서는 그대로 유지되어야 하며, 패턴에 없는 대문자가 쿼리에 포함되면 일치할 수 없습니다.
예시로 이해하기
예를 들어 쿼리 목록이 ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"]이고 패턴이 "FB"라고 가정해 보겠습니다. 이때 기대되는 출력은 [true, false, true, true, false]입니다.
- FooBar → true : "F"와 "B" 사이에 소문자 "oo"와 "ar"를 삽입하면 됩니다.
- FooBarTest → false : 패턴에 없는 대문자 "T"가 포함되어 있어 일치할 수 없습니다.
- FootBall → true : "F"와 "B" 사이에 "oot"를, 뒤에 "all"을 삽입하면 성립합니다.
- FrameBuffer → true : "F"와 "B" 사이에 "rame"를 삽입하고 뒤에 "uffer"를 붙이면 됩니다.
- ForceFeedBack → false : 첫 번째 "F" 다음에 패턴의 "B"가 아닌 또 다른 대문자 "F"가 등장하므로 일치하지 않습니다.
풀이 전략: 트라이(Trie) 자료구조
이 문제는 트라이(접두사 트리)를 활용하면 깔끔하게 해결할 수 있습니다. 먼저 패턴을 트라이에 삽입한 뒤, 각 쿼리 문자열을 한 글자씩 순회하며 트라이를 따라 내려갑니다. 이때 적용되는 규칙은 다음과 같습니다.
- 현재 노드에 해당 문자의 자식이 존재하면 그 자식으로 이동합니다.
- 자식이 존재하지 않고 해당 문자가 대문자라면, 패턴에 없는 대문자가 끼어든 것이므로 매칭에 실패합니다(ok = false).
- 자식이 존재하지 않고 해당 문자가 소문자라면, 쿼리에 삽입된 소문자이므로 무시하고 계속 진행합니다.
- 순회가 끝난 후 현재 노드가 단어의 끝(isEnd)이고 실패 플래그가 설정되지 않았다면 true를 저장합니다.
알고리즘 단계
- insertNode() 메서드를 정의합니다. 이 메서드는 헤드(head) 노드와 문자열 s를 인자로 받습니다.
- curr := head로 초기화합니다.
- i를 0부터 s의 크기 - 1까지 반복합니다.
- x := s[i]
- curr의 child[x]가 null이라면 새 노드를 생성하여 child[x]에 할당합니다.
- curr := curr의 child[x]로 이동합니다.
- curr의 isEnd를 true로 설정합니다.
- 메인 로직에서는 head := 새 노드를 생성하고 패턴을 삽입합니다. n := 쿼리 배열의 크기, m := 각 쿼리(temp)의 크기, ok := true로 초기화합니다.
- j를 0부터 m - 1까지 반복합니다.
- x := temp[j]
- curr의 child[x]가 존재하면 curr := curr의 child[x]로 이동합니다.
- 존재하지 않는데 temp[j]가 'A'~'Z' 범위의 대문자라면 ok := false로 설정하고 반복문을 탈출합니다.
- ans[i] := curr의 isEnd AND ok로 저장합니다.
- ans를 반환합니다.
C++ 구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class Solution {
public:
void insertNode(Node* head, string s){
Node* curr = head;
for(int i = 0; i < s.size(); i++){
char x = s[i];
if(!curr->child[x]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
vector<bool> camelMatch(vector<string>& queries, string pattern){
Node* head = new Node();
insertNode(head, pattern);
int n = queries.size();
vector <bool> ans(n);
Node* curr;
bool ok;
for(int i = 0; i < n; i++){
string temp = queries[i];
curr = head;
int m = temp.size();
ok = true;
for(int j = 0; j < m; j++){
char x = temp[j];
if(curr->child[x]){
curr = curr->child[x];
}
else if(temp[j] >= 'A' && temp[j] <= 'Z'){
ok = false;
break;
}
}
ans[i] = curr->isEnd && ok;
}
return ans;
}
};
main(){
vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
Solution ob;
print_vector(ob.camelMatch(v1, "FB"));
}
실행 결과
입력
["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
"FB"
출력
[1, 0, 1, 1, 0]
출력에서 1은 true, 0은 false를 의미합니다. 즉, FooBar, FootBall, FrameBuffer 세 단어만 패턴 "FB"와 일치함을 확인할 수 있습니다.
복잡도 분석
패턴의 길이를 M, 모든 쿼리 문자열 길이의 합을 N이라고 할 때, 트라이 구축에 O(M), 각 쿼리 순회에 쿼리 길이만큼의 시간이 걸리므로 전체 시간 복잡도는 O(N + M)입니다. 공간 복잡도 역시 트라이 저장에 O(M)이 필요합니다. 이처럼 트라이를 활용하면 각 쿼리를 선형 시간에 효율적으로 검증할 수 있습니다.