DFA(결정적 유한 오토마타, Deterministic Finite Automaton)를 활용하면 "THE"라는 부분 문자열로 끝나지 않는 문자열을 효율적으로 판별할 수 있습니다. 이때 중요한 점은 tHe, The, ThE처럼 대소문자 조합이 다른 모든 변형 역시 문자열의 끝에 나타나서는 안 된다는 것입니다.
DFA 상태 설계 개요
이 문제의 DFA는 총 4개의 상태(0~3)로 구성됩니다.
- 상태 0 : 시작 상태 — 아직 어떤 문자도 일치하지 않음
- 상태 1 : 'T'까지 일치
- 상태 2 : 'TH'까지 일치
- 상태 3 : 'THE'까지 일치 — 문자열 거부
문자열을 앞에서부터 한 글자씩 읽으며 상태를 전환하고, 모든 문자를 처리한 뒤 최종 상태가 3이 아니라면 해당 문자열은 "THE"로 끝나지 않는 것이므로 받아들여집니다. 이 방식은 문자열을 한 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다.
1. 상태 추적 변수 초기화
먼저 현재 상태를 추적할 dfa 변수를 선언하고 0으로 초기화합니다. 일치하는 문자가 입력될 때마다 이 값이 다음 상태로 갱신됩니다.
int dfa = 0;
2. begin() 함수 — 시작 상태 처리
begin(char c) 함수는 입력된 문자가 't' 또는 'T'인지 확인하고, 해당하면 첫 번째 상태(1)로 전환합니다.
void begin(char c){
if (c == 't' || c == 'T')
dfa = 1;
}
3. firstState() 함수 — 상태 1 처리
firstState(char c) 함수는 상태 1('T'까지 일치)일 때 입력되는 문자를 검사하여 dfa 값을 갱신합니다.
- 't' 또는 'T'면 상태 1 유지 (새로운 'T' 접두사 검사 시작)
- 'h' 또는 'H'면 상태 2로 전환 ('TH'까지 일치)
- 그 외의 문자면 시작 상태인 0으로 복귀
void firstState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else if (c == 'h' || c == 'H')
dfa = 2;
else
dfa = 0;
}
4. secondState() 함수 — 상태 2 처리
secondState(char c) 함수는 상태 2('TH'까지 일치)에서 입력되는 문자를 확인합니다. 'e' 또는 'E'가 들어오면 세 번째 상태(3)로 전환하고, 그렇지 않으면 시작 상태(0)로 돌아갑니다.
void secondState(char c){
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
5. thirdState() 함수 — 상태 3 처리
thirdState(char c) 함수는 상태 3('THE'까지 일치)에서 추가 문자가 입력될 때 호출됩니다. 새 문자가 't' 또는 'T'라면 상태 1로 이동해 새로운 접두사 검사를 시작하고, 그 외의 문자라면 시작 상태(0)로 복귀합니다.
void thirdState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
6. isAccepted() 함수 — 전체 문자열 검사
isAccepted(string str) 함수는 검사할 문자열을 매개변수로 받습니다. len 변수에 문자열 길이를 저장한 뒤, for 루프로 문자열을 처음부터 끝까지 순회하면서 현재 dfa 값에 따라 적절한 상태 함수를 호출합니다.
- dfa == 0 → begin() 호출
- dfa == 1 → firstState() 호출
- dfa == 2 → secondState() 호출
- dfa == 3 → thirdState() 호출
순회가 끝난 후 dfa가 3이 아니면 true를 반환합니다. 즉, 문자열이 "THE"로 끝나지 않으면 받아들여지고, 3이라면 거부됩니다.
bool isAccepted(string str){
int len = str.length();
for (int i=0; i < len; i++) {
if (dfa == 0)
begin(str[i]);
else if (dfa == 1)
firstState(str[i]);
else if (dfa == 2)
secondState(str[i]);
else
thirdState(str[i]);
}
return (dfa != 3);
}
전체 예제 코드
다음은 "THE"로 끝나지 않는 문자열을 판별하는 DFA의 전체 구현입니다.
#include <iostream>
#include <string>
using namespace std;
int dfa = 0;
void begin(char c){
if (c == 't' || c == 'T')
dfa = 1;
}
void firstState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else if (c == 'h' || c == 'H')
dfa = 2;
else
dfa = 0;
}
void secondState(char c){
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
void thirdState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
bool isAccepted(string str){
int len = str.length();
for (int i=0; i < len; i++) {
if (dfa == 0)
begin(str[i]);
else if (dfa == 1)
firstState(str[i]);
else if (dfa == 2)
secondState(str[i]);
else
thirdState(str[i]);
}
return (dfa != 3);
}
int main(){
string str = "helloForTheWorld";
if (isAccepted(str) == true)
cout<<"The string "<<str<<" is accepted ";
else
cout<<"The string "<<str<<" is not accepted";
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
The string helloForTheWorld is accepted
예제 문자열 "helloForTheWorld"는 중간에 "The"를 포함하고 있지만, 문자열의 마지막 부분("World")이 "THE"가 아니므로 최종 상태가 3에 도달하지 않아 정상적으로 받아들여집니다. 만약 문자열이 "helloForTHE"처럼 "THE"(대소문자 무관)로 끝난다면 최종 상태가 3이 되어 거부됩니다.