[백준] 1013번: Contact (java)

1013번: Contact (acmicpc.net)

1013번: Contact

어떻게 생각하고 문제를 풀었는가?

(100+1+|01)+의 패턴을 검사하는 문제이지만 10011001와 같은 입력에 대해서 10011로 패턴을 확인할 것인지, 1001로 패턴을 확인할 것인지에 따라서 결과가 달라질 수 있습니다.

따라서 정규표현식으로 패턴을 확인하기보다 유한 상태 장치를 구현하여 문제를 해결하고자 하였습니다.

코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Solution sol = new Solution();
        StringBuilder sb = new StringBuilder();
        while(N-->0){
            sb.append(sol.isPattern(br.readLine())? "YES\n" : "NO\n");
        }
        System.out.println(sb.toString());
        br.close();
    }
}
class Solution{
    public boolean isPattern(String str){
        char state = 'A';
        for(char ch : str.toCharArray()){
            state = next(state,ch);
            if(state>'I') return false;
        }
        return (state=='I'||state=='E'||state=='F');
    }
    private char next(char state, char ch){
        switch (state){
            case 'A':
                return ch=='1'? 'B' : 'H';
            case 'B':
                return ch=='1'? 'Z' : 'C';
            case 'C':
                return ch=='1'? 'Z' : 'D';
            case 'D':
                return ch=='1'? 'E' : 'D';
            case 'E':
                return ch=='1'? 'F' : 'H';
            case 'F':
                return ch=='1'? 'F' : 'G';
            case 'G':
                return ch=='1'? 'I' : 'D';
            case 'H':
                return ch=='1'? 'I' : 'Z';
            case 'I':
                return ch=='1'? 'B' : 'H';
        }
    return 'Z';
    }
}

유한 상태 장치를 구현한 코드입니다.

현재 문자가 어떤 패턴의 문자에 해당하는지를 상태로서 저장함으로써 문자열이 패턴에 해당하는지 확인하여 결과를 반환합니다.

각 문자를 순환하며 패턴에 일치하지 않는 문자가 나타나면 'Z' 상태가 되며 false를 반환, 모든 문자를 순환했다면 (100+1+ | 01)+의 패턴이 되도록 E, F, I의 상태일 경우에만 true를 반환합니다.

아래의 그림은 시작 상태 'A'에서 시작하여 순환하는 유한 상태 장치입니다.

 

(100+1+ 01)+를 탐색하는 유한 상태 장치