백준 1013 Contact

출처: https://www.acmicpc.net/problem/1013

분류: 문자열, 오토마타, 정규식

---

접근방식

처음에 일일이 경우의 수를 따라가면서 해주려고 했는데 너무 복잡해서 다른 분들은 어떻게 똑똑하게 푸셨는지 열심히 참고했습니다...

결국 각 단계를 State로 하는 오토마타를 그려서 해결했습니다!

 

발로그린.... 🤐

 

6번 다음에 1로 보내야 할지 6에서 반복을 돌려야 할지 문제였는데 7이라는 새로운 state로 넘겨서 새로운 분기를 만들어주는 방식이 있네요!!

2번에서 0이 나왔을 때 1로 넘겨주는 것도 주의해야 합니다 :)

 

참고

https://maivve.tistory.com/208

 

해결방법

let n = Int(readLine()!)!

func isValidPattern(_ pattern: String) -> Bool {
    // (100+1+ | 01)+
    var state = 0
    for char in pattern {
        if let nextState = next(flag: char, from: state) {
            state = nextState
        } else {
            return false
        }
    }
    
    return [0, 2, 6, 7].contains(state)
}

func next(flag: Character, from state: Int) -> Int? {
    if flag == "0" {
        switch state {
            case 0: return 1
            case 1: return nil
            case 2: return 1
            case 3: return 4
            case 4: return 5
            case 5: return 5
            case 6: return 1
            case 7: return 8
            case 8: return 5
            default: return nil
        }
    } else {
        switch state {
            case 0: return 3
            case 1: return 2
            case 2: return 3
            case 3: return nil
            case 4: return nil
            case 5: return 6
            case 6: return 7
            case 7: return 7
            case 8: return 0
            default: return nil
        }
    }
}

for _ in 0..<n {
    let pattern = readLine()!
    print(isValidPattern(pattern) ? "YES" : "NO")
}

 

배운점

어렵드아....