문자열이 조건을 충족시키는지 확인하는 문제였다. 정규식만 알고 있다면 쉽게 풀 수있는 문제였다. 정규식 말고 다른 방법이 없을까 다른 사람들의 풀이를 찾던 중 재밌는 방법을 발견해서 공부겸 글을 작성해본다.
그 방법은 바로 Deterministic Finite Automata이다. Automata 앞에 Deterministic과 Finite이 있느 것을 보면 비결정적이고 무한한 Automate도 있는 것 같아서 살펴보았지만 공부의 깊이가 깊어지는 것 같아서 다음에 살펴보기로 기약했다.
Automata는 특정 상태에서 어떤 값에따라 다른 상태로 변화하는 것을 정리한다.
A 상태에서 0 또는 1 값을 받으면 다음으로 어떤 상태로 변이하는지 나타낸 그림이다. 마지막 상태값이 0,3,6,7 인 경우만 조건을 만족하고 있다.
package com.test.backjun;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Pattern;
public class Baek1013 {
// 1. 정규식으로 푸는 방법
// 2. 오토마타 ? 처음 듣는 방법, 문자열을 하나씩 읽어나가며서 상태를 바꾼다. 모로가도 안되는 상태가 되면 끝...
public static void main(String[] args) throws Exception{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// (100+1+ | 01)+
// regex(reader);
automata(reader);
}
// 1. 정규식
public static void regex(BufferedReader reader) throws Exception{
int n = Integer.parseInt(reader.readLine());
StringBuilder sb = new StringBuilder();
Pattern p = Pattern.compile("^(100+1+|01)+$");
for (int i = 0; i < n; i++) {
String v = reader.readLine();
if(p.matcher(v).matches()){
sb.append("yes");
}else{
sb.append("no");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
// 2. DFA
public static void automata(BufferedReader reader)throws Exception {
int n = Integer.parseInt(reader.readLine());
StringBuilder sb = new StringBuilder();
// auto의 첫번째 array는 상태값
// auto의 상태값 안의 값은 입력값에 따른 다음 상태로 전이할 상태값
// 조건에 부합하지 않는 문자열은 -1 반환
int[][] auto = new int[][]{
{1,2},// 상태 0
{-1,3},// 상태 1
{4,-1},// 2
{1,2},// 3
{5,-1},// 4
{5,6},// 5
{1,7},// 6
{8,7},// 7
{5,0},// 8
};
for (int i = 0; i < n; i++) {
String v = reader.readLine();
int state =0 ;
for (int j = 0; j < v.length(); j++) {
state = auto[state][v.charAt(j)-'0'];
if (state <0){
break;
}
}
if(state ==0|| state ==3 || state==6 || state==7){
sb.append("YES");
}else{
sb.append("NO");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
참고 자료들
https://maivve.tistory.com/208
https://velog.io/@haribo/%EB%B0%B1%EC%A4%80-1013-Contact
DFA, NFA 등 추가적으로 공부할 내용들
https://sweetdev.tistory.com/910
https://dokhakdubini.tistory.com/451