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

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 3⋅105)
• a b (길이 n, consisting of symbols 0 and 1)

output :

• For each test case, output "YES" if it is possible to transform a into b, or "NO" if it is impossible. You can print each letter in any case (upper or lower).
  a 문자열을 b로 만들 수 있다면 "YES"를 그렇지 않은 경우엔 "NO"를 출력하시오.

조건 :

• There is a binary string a of length n. In one operation, you can select any prefix of a with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0.
  이진수로 이루어진 문장 a가 존재한다. 연산을 수행할 시 1과 0의 수가 동일한 접두사를 선택하여 이 부분을 이루는 0의 경우 1로 1의 경우 0으로 교체한다.

뒤에서 부터 동일하지 않은 부분 까지를 찾아서 뒤집고 뒤집으려 했다. 이렇게 할 경우 코드도 길어지고 시간 복잡도도 많이 필요하다. 다른 방법이 필요하다.

교체가 필요

교체가 필요한 경우를 따져보자.
접두사 부분에서 현재 인덱스에 있는 문자가 다르다면 교체를 해야 한다. 그런데 현재 위치가 아니라 현재 위치 + 1이 다르다면? 현재 위치까지의 접두사를 뒤집어야 그 다음 +1 에서 뒤집을 떄 원래 모양을 얻을 수 있다.

이러한 경우를 생각해야 한다.

교환

인덱스를 이렇게 볼 떄

이러한 형태를 유지한다면 교환을 해야 한다. 근데 이 때 교환을 할 수 있는 조건을 만족하지 않는다면? 만들 수 없는 것이다.

이를 boolean값을 사용해서 계산하자.,

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    a = list(sys.stdin.readline().rstrip())
    b = list(sys.stdin.readline().rstrip())
    a.append('1')
    b.append('1')
    cnt, flag = 0, 0

    for i in range(n):
        cnt += (a[i] == '1') - (a[i] == '0')

        if ((a[i] == b[i]) != (a[i + 1] == b[i + 1])) and cnt != 0:
            flag = 1
            break

    print("NO" if flag else "YES")

맨 뒤에 동일한 값을 추가함으로써 계산을 훨씬 편하게 하도록 하자.