백준 1013 : Contact

풀이1 : TypeError

• 정규표현식을 사용
• 1
  100111001 같은 반례가 존재한다(YES가 나와야 한다).
• TypeError의 원인은 match함수의 반환값이 null이 나올 수 있기 때문인 것 같다.

var fs = require("fs")


const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');

let caseNum = stdin[0];


// (100+1+ | 01)+ 여부를 반환해야 한다.
//+는 앞의 문자가 최소 1번 이상 반복됨을 의미
function isMatch(str){
    const regexp = /(100{1,}1{1,}){1,}|(01){1,}/g
    let matStr = str.match(regexp);
    //matStr을 join한 결과값이 원래 문자열과 같다면, 조건을 만족한다.
    return (matStr.reduce((acc, cur) => acc+cur,"") === str);
}

for(let i = 1; i <= caseNum; i++){
    if(isMatch(stdin[i])) console.log("YES");
    else console.log("NO");
}

풀이2

• 다른 언어의 정규표식과 자바스크립트의 test함수의 작동이 차이가 있어서('+'가 탐욕적으로 작용한다) DFA(결정적 유한 오토마타, Deterministic finite automaton)을 이용하기로 했다.
• DFA는 Q, Σ,δ,q0(s0),F로 구성되어있다.
  • Q : q0~q9까지 상태들의 집합
  • Σ : 입력 문자(이 문제에서는 0,1)
  • δ(델타) : 상태 전이 함수. 어떤 state로 가게 될지 알려주는 함수
  • q0(s0) : 초기 상태. Q의 원소이다.
  • F : 최종 상태의 집합(여러 개일 수 있다.). Q의 원소이다. 아래 그림에서는 동그라미가 두 개 그려진 q5, q6, q7이다

    출처
    https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84

• 예시로 주어진 케이스들을 확인하면서 state들을 추가했다. 특히 6, 8, 9번의 state가 애를 먹였다.

var fs = require("fs")

const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');

let caseNum = stdin[0];

//2차원 배열의 형태이며, 행은 현재 state, 
//열의 0번째 요소는 '0'이라는 문자열이 주어진 뒤 상태,
//열의 1번째 요소는 '1'이라는 문자열이 주어진 뒤의 상태이다.
let dfs = [
    [2, 1],
    [3, 8],
    [8, 7],
    [4, 8],
    [4, 5],
    [2, 6],
    [9, 6],
    [2, 1],
    [8, 8],
    [4, 7]
]

function isMatch(str){
    //상태의 초기값
    let curState = 0;
    for(let c of str){
        if(c === "0"){
            curState = dfs[curState][0];
        } else if(c === "1"){
            curState = dfs[curState][1];
        }
    }

    //탐색이 끝난 후, F의 집합에 속할 경우
    if(curState === 5 || curState === 6 || curState === 7) return true;
    return false;
}



for(let i = 1; i <= caseNum; i++){
    if(isMatch(stdin[i])) console.log("YES");
    else console.log("NO");
}