이 글에서는 문자 스트림을 실시간으로 처리하는 StreamChecker 클래스를 C++로 구현하는 방법을 알아보겠습니다.
문제 정의
StreamChecker 클래스는 다음 두 가지 기능을 제공해야 합니다.
StreamChecker(words) — 생성자입니다. 주어진 단어 목록으로 자료구조를 초기화합니다.
query(letter) — 지금까지 질의한 문자 중 마지막 k개(가장 오래된 것부터 최신 것까지 순서대로, 방금 질의한 문자 포함)를 이어 붙였을 때 단어 목록 속 단어 하나와 일치하는 k ≥ 1이 존재하면 true를 반환합니다.
예시
단어 목록이 ["ce", "g", "lm"]이고, query()를 문자 [a, b, c, e, f, g, h, i, j, k, l, m] 순서로 여러 번 호출한다고 가정해 봅시다. 그러면 e, g, m에 대해서는 true가 출력되고, 나머지 문자에 대해서는 false가 출력됩니다.
해결 접근 방식
이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재까지 입력된 문자열의 접미사(suffix) 중 트라이 위에서 진행 중인 경로들을 별도의 대기 목록(waitList)으로 관리하는 것입니다. 새 문자가 들어올 때마다 대기 중인 모든 노드를 해당 문자로 확장해 보고, 확장에 실패한 경로는 자연스럽게 제거합니다.
구현 단계는 다음과 같습니다.
- 노드 구조체를 정의합니다. 각 노드는 26개의 자식 노드 배열과 단어 끝 여부를 나타내는 isEnd 플래그를 가집니다.
- 초기 상태에서 isEnd는 false이며, 자식 배열은 모두 null로 채웁니다.
- 트라이의 루트가 될 head 노드를 선언합니다.
- 매칭 진행 상태를 추적할 노드 배열 waitList를 준비합니다.
- insertNode() 함수를 정의합니다. head와 문자열 s를 받아 단어를 트라이에 삽입합니다.
- curr := head로 시작합니다.
- i := 0부터 s의 길이 미만까지 반복하면서 다음을 수행합니다.
- x := s[i]
- curr의 child[x - 'a']가 null이면 새 노드를 생성해 연결합니다.
- curr := curr.child[x - 'a']로 이동합니다. - 반복이 끝나면 curr.isEnd := true로 설정합니다.
- 생성자에서는 다음 작업을 수행합니다.
- head := 새 노드 생성
- words의 모든 단어에 대해 insertNode(head, words[i]) 호출
- curr := head로 초기화
- query() 함수를 정의합니다. 이 함수는 문자 x를 받아 다음 과정을 거칩니다.
- 노드 배열 temp를 하나 만듭니다.
- head의 child[x - 'a']가 존재하면 head를 waitList 끝에 추가합니다(새 매칭 시작).
- ret := false로 초기화합니다.
- waitList의 각 노드에 대해 다음을 수행합니다.
- curr := waitList[i]
- curr의 child[x - 'a']가 존재하면 curr를 해당 자식으로 이동시키고, temp에 추가한 뒤 ret := ret OR curr.isEnd로 갱신합니다. - 확장하지 못한 경로는 temp에 담기지 않으므로 자동으로 제거됩니다.
- temp와 waitList를 교환(swap)한 뒤 ret을 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* child[26];
bool isEnd;
Node(){
isEnd = false;
for (int i = 0; i < 26; i++)
child[i] = NULL;
}
};
class StreamChecker {
public:
Node* head;
vector<Node*> waitList;
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 - 'a']) {
curr->child[x - 'a'] = new Node();
}
curr = curr->child[x - 'a'];
}
curr->isEnd = true;
}
StreamChecker(vector<string>& words){
head = new Node();
for (int i = 0; i < words.size(); i++) {
insertNode(head, words[i]);
}
Node* curr = head;
}
bool query(char x){
vector<Node*> temp;
if (head->child[x - 'a']) {
waitList.push_back(head);
}
bool ret = false;
for (int i = 0; i < waitList.size(); i++) {
Node* curr = waitList[i];
if (curr->child[x - 'a']) {
curr = curr->child[x - 'a'];
temp.push_back(curr);
ret |= curr->isEnd;
}
}
swap(temp, waitList);
return ret;
}
};
main(){
vector<string> v = {"ce","g","lm"};
StreamChecker ob(v);
cout << (ob.query('a')) << endl;
cout << (ob.query('b')) << endl;
cout << (ob.query('c')) << endl;
cout << (ob.query('e')) << endl;
cout << (ob.query('f')) << endl;
cout << (ob.query('g')) << endl;
cout << (ob.query('h')) << endl;
cout << (ob.query('i')) << endl;
cout << (ob.query('j')) << endl;
cout << (ob.query('k')) << endl;
cout << (ob.query('l')) << endl;
cout << (ob.query('m'));
}
입력
"ce", "g", "lm", query()
출력
0 0 0 1 0 1 0 0 0 0 0 1
출력 결과를 보면 네 번째 질의(e), 여섯 번째 질의(g), 열두 번째 질의(m)에서만 1(true)이 반환되고, 나머지 질의에서는 0(false)이 반환됩니다. 이는 "ce"가 c 다음 e에서, "g"가 g에서, "lm"이 l 다음 m에서 완성되기 때문입니다. 이처럼 트라이와 대기 목록을 활용하면 각 질의를 O(대기 경로 수) 시간 안에 빠르게 처리할 수 있습니다.