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")
