B. Binary Removals | Edu Round #106 Div.2

https://codeforces.com/contest/1499/problem/B
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 1000)
• s (2 ≤ |s| ≤ 100)

output :

• For each testcase print "YES" if there exists a sequence a such that removing the characters at positions a1, a2, …, ak and concatenating the parts without changing the order produces a sorted string.
  Otherwise, print "NO".
  각 테스트 케이스에서 임의의 위치에 존재하는 문자들을 제외했을 떄 여전히 정렬된 문자열을 얻을 수 있다면 "YES"를 그렇지 않은 경우에는 "NO"를 출력하시오.

조건 :

• You are asked to choose some integer k (k > 0) and find a sequence a of length k such that:
  1 ≤ a1 < a2 < ⋯ < ak ≤ |s|;
  ai − 1 + 1 < ai for all i from 2 to k.
  임의의 k를 골라 길이 k를 가지는 배열을 찾으시오. 이 때에 조건이 2가지 있는데 인덱스들은 증가해야 하고 인덱스의 차이가 1보다 커야 한다.

• Let the resulting string be s'. s' is called sorted if for all i from 2 to |s'|
  s'i − 1 ≤ s'i.
  위의 배열을 제거하고 얻은 문자열이 s'이라 할 때 s'의 모든 원소들에 대해 이전의 원소들이 이후의 원소와 같거나 크면 정렬되었다고 한다.

무엇을 원하는 문제인지 판단하는 것이 어려웠다.

일단 우선적으로 정렬이 되었다는 것이 어떤것인지를 알아야하는데. 문제의 조건에서 알 수 있듯이 000....111과 같이 이루어진것을 정렬된것이라 본다.
혹은 111111
혹은 000000 과 같은 문자열이어야 한다.

그렇다면 안 되는 경우를 알면 될 것 같은데 안 되는 경우는? 111...00 의 경우이다. 삭제 하는 것들의 인덱스가 1, 3, 5, 7 ... 처럼 최소한 한 칸을 두고 가기 때문에 11처럼 붙어있는 경우에 최소한 하나는 남게 된다.

그래서 붙어 있는 문자열의 위치를 확인하자.

11, 00 의 문자열이 가장 먼저 나오는, 나중에 나오는 위치를 찾아 둘을 비교한다.

import sys

for _ in range(int(sys.stdin.readline())):
    data = sys.stdin.readline().rstrip()
    zero_idx, one_idx = -1, 101

    for j in range(1, len(data)):
        if data[j] == '0' and data[j] == data[j - 1]:
            zero_idx = max(zero_idx, j)
        elif data[j] == '1' and data[j] == data[j - 1]:
            one_idx = min(one_idx, j)

    print("NO" if zero_idx > one_idx else "YES")