[문자열] Python - 1013번 Contact

N = int(input())
for i in range(N):
    cur = input()
    idxCur = 0 #100+1+ 또는 01의 시작 부분을 가리키도록 설계
    prtCur = 'YES'
    while idxCur < len(cur):
        if cur[idxCur]=='0': #01
            if idxCur+1<len(cur) and cur[idxCur+1]=='1':
                idxCur+=2
            else:
                prtCur = 'NO'
                break
        elif cur[idxCur]=='1': #100+1+
            try:
                if cur[idxCur+1]=='0' and cur[idxCur+2]=='0': #100
                    idxCur+=3
                else:
                    prtCur = 'NO'
                    break

                if cur[idxCur]=='0': #0+
                    while cur[idxCur]=='0':
                        idxCur+=1

                if cur[idxCur]=='1': #1
                    idxCur+=1
                else:
                    prtCur = 'NO'
                    break
                    
                if idxCur<len(cur) and cur[idxCur]=='1': #1+
                    while idxCur<len(cur) and cur[idxCur]=='1':
                        idxCur+=1
                    if idxCur+1<len(cur): #(idxCur이 0을 가리키고 있음)
                        if cur[idxCur+1]=='0': #11111/100...
                            idxCur-=1
                        elif cur[idxCur+1]=='1': #111111/01
                            idxCur+=2
            except: #길이가 짧아서 out of index 오류가 범해지는 경우.
                prtCur = 'NO'
                break

    print(prtCur)

# try - except절 내의 if문들 중, idxCur<len(cur) 같은 조건을 통해 out of index 에러가 나지 않게 만든 조건들은 의도한 바입니다. 결국 out of index가 발생했다는 것은, 1001이라는 최소 길이보다 짧다는 것을 의미합니다.(ex 100, 10, 11)

 

 

아쉬운 점이 많습니다.

우선 python에서 regex을 써보지 않아서 이렇게 지엽적인 풀이로 풀 수밖에 없었다는 것입니다.(검색이라는 선택지가 있으나, 저는 검색을 허용하지 않는 코딩테스트를 보고 있다는 전제 하에 문제 풀이를 실시합니다.)

또한, 전혀 일반화가 되지 않은 풀이였기 때문에 코드도 난잡해져서 정답을 맞혔음에도 기분이 썩 좋진 않았고요.

마지막으로 time complexity 또한 전체의 중간 수준에 불과하네요.

 

이 문제처럼 regex가 '100+1+'로 한정되지 않았을 경우에도 일반화하여 풀 수 있었을지 의문입니다.

python의 re library를 익혀야할 계기가 마련됐습니다.

 

+re를 통해 regex로 손쉽게 풀어보았으나, 시간 복잡도가 되려 높아지네요. 이 문제에서 시간 복잡도를 가져가려면 'state'라는 개념을 써야하네요. 간단하게 알아보자면 다음과 같습니다.

(위 사진에서 A->D로 이어지는 부분 이후는 생략하였습니다.)

State A에서 시작되며, 일정 State에서 도달할 수 있는 State가 정해져있는 모델을 만드는 것입니다.

0101은 A -> B -> C -> B -> C의 경우라고 보시면 되겠습니다.