[백준] 1013 Contact, python

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

1013번: Contact

문자열 문제이고 정규표현식(regex, regular expression)으로 풀었다.

 

쉽게 풀줄 알았으나 match를 사용하면 패턴을 제대로 찾지 못하는 값들이 있었다. 예를 들면 '100111001' 이런 문자열이 들어왔을 때  '10011' '1001' 로 나눌수 있기 때문에 True 값이 나와야한다. 하지만 정규 표현식은 탐욕적으로 값을 구하기 때문에 '100+1+' 패턴중 가장 긴 패턴인 '100111'을 찾아서 반환 시킨다. 그래서  그 뒤의 '001' 이라는 문자열에선 값을 찾을수 없게되고 False 값을 반환한다. (내가 풀다 깨우친건 아니고 백준 질문게시판을 찾다가 알게된 사실이다. )

이를 해결하기 위해 시작점을 변수로 해서 문자열 slicing으로 패턴을 계속 찾았다. 시작 인덱스가 중간 값들을 가질 땐 '11' 으로 끝나는 패턴에선 end-1을 더한 값으로 시작하게 했고 그 외의 패턴에선 end를 더한값으로 시작했다.(값을 더하는 이유는 문자열을 슬라이싱하기때문에 시작 값이 항상 0이어서 누적값으로 갱신해야한다.)

그리고 슬라이싱 한 문자열에서 패턴을 찾을 수 없으면 바로 False값이 나오도록 했고, 전체 문자열이 매치된경우 True 값이 나오도록했다.

import sys; input = sys.stdin.readline
import re
p = re.compile('(100+1+|01)+')

def pattern_check(s):
    i = 0
    while i < len(s):
        m = p.match(s[i:])
        if not m:
            return False
        if m.end() == len(s):
            return True
        if s[m.end() - 1] == '1':
            if s[m.end() - 2] == '1':
                i += m.end() - 1
            else:
                i += m.end()
        else:
            i += m.end()

    return True

def main():
    T = int(input())
    for _ in range(T):
        s = input().rstrip()
        print("YES" if pattern_check(s) else "NO")



if __name__ == "__main__":
    main()

 

이런 문제가 있기 때문에 python regex에서는 fullmatch라는 함수도 있다. 전체 문자열과 길이가 같은 경우를 찾기때문에 직접 함수를 만들지 않아도 된다

import sys; input = sys.stdin.readline
import re
p = re.compile('(100+1+|01)+')

def main():
    T = int(input())
    for _ in range(T):
        s = input().rstrip()
        print("YES" if p.fullmatch(s) else "NO")

if __name__ == "__main__":
    main()

---

속도가 빠른 알고리즘은 index로 접근해서 직접 패턴을 확인하는 알고리즘이었다. 오래 걸릴거같으니 패스하겠다.