[백준 1013] Contact

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    code = input().rstrip()
    l = len(code)
    i = 0
    ch = True

    while i < l :
        # 시작이 0인경우 바로 뒤에 1이 안오면 실패
        if code[i] == "0":
            #남은 수가 2개가 안될 때 실패(01이 최소 길이기 때문)
            if l-i < 2:
                ch=False
                break
            elif code[i+1] != "1":
                ch=False
                break
            else:
                i+=2
        # 시작이 1이 올경우
        else:
            #남은 수가 4개가 안될 때 실패(1001이 최소 길이기 때문)
            if l-i < 4:
                ch=False
                break
            # 다음 2개가 0이 아닐결우 실패
            elif code[i+1] != "0" or code[i+2] != "0":
                ch=False
                break
            else:
                i+=2 # 0,0 추가
                while code[i] != "1": # 1찾기
                    i+=1
                    #1을 못찾고 0으로 끝나면 실패
                    if i==l:
                        ch=False
                        break
                
                if not ch:
                    break

                # 현재 code[i] == 1 , 1까지 찾은 상태

                while code[i] != "0": # 0찾기
                    i+=1
                    if i==l:
                        break
                
                # 현재 code[i] == 0
                
                # 100패턴으로 이어질경우 i 위치를 다시 1로 맞춰준다.
                if i+1 < l and code[i-2] == "1" and code[i+1] == "0":
                    i-=1
                    
    if ch:
        print("YES")
    else:
        print("NO")

www.acmicpc.net/problem/1013

1013번: Contact

풀이

 

포인터를 두고 왼쪽부터 탐색한다.

 

첫 번째 규칙은 시작부분이 0이 나오면 바로 뒤에 1이 나와야 통과한다는 것

 

두 번째 규칙은 시작부분이 1이 나오면 '100 (0000....)~~~ 1 (1111....)' 형식이니 0이 두번 이상 나오고 이후에 1이 최소 1개 나와야 한다는 것이다.

 

2가지의 규칙으로 풀면 예외를 처리할 수 없다.(여기서 시간을 많이 뺏겼다)

 

바로 1001 1001 같이 두 번째 규칙이 반복하는 경우를 찾을 수 없다.

 

'10011' 까지 처리해버리면 남아있는 001 은 맞지 않는 규칙이니 'NO'가 출력된다.

 

하지만 이것은 '1001' '1001' 이 합쳐진 것으로 사실은 규칙에 맞는 'YES'이다.

 

그래서 1로 시작하며 1로 끝날때 경우를 나눠줘야한다.

 

10011001 현재 탐색 인덱스 i가 5의 위치에 있다고 해보자.

두 번째 규칙이 반복되는경우에는 무조건 i-2 이 1이고 i+1이 0이다.

 

두 번째 규칙이 반복되는 경우라면 i-1을 해줘 탐색 인덱스를 1줄여준다.

그러면 i의 위치는 10011001 로 이동할 것이다.

 

그러면 다시 1로 시작하는 규칙으로 인식되어 'YES'를 출력하게 된다.

 

시간복잡도

문자열을 한바퀴 돌리면 될 뿐이니 O(N)이다.