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

input :

• q (1 ≤ q ≤ 105)
• s (1 ≤ |s| ≤ 105)
• t (1 ≤ |t| ≤ 105)

output :

• For each test case, print "YES" if you can obtain the string t by typing the string s and replacing some characters with presses of "Backspace" button, or "NO" if you cannot.
  s를 입력하고 삭제하면서 t를 얻을 수 있다면 "YES"를 그렇지 않다면 "NO"를 출력하시오.

조건 :

• When typing a character, instead of pressing the button corresponding to it, you can press the "Backspace" button. It deletes the last character you have typed among those that aren't deleted yet (or does nothing if there are no characters in the current string)
  동일한 문자를 입력하지 않는 경우 "Backspace"를 입력할 수 있습니다. 이는 지금까지 입력한 문자들 중 가장 마지막 문자를 삭제합니다.

아주 짜증난다..
우선적으로 내가 생각한 방식을 작성해보겠다.

동일한 문자

앞에서 부터 인식을 해서 t와 동일한 문자를 가진 놈들부터 모두를 확인하면 당연히 정답을 얻을 수 있겠다 싶었다. (물론, 이게 가장 큰 패인이다. 문장의 길이를 제대로 생각하지 않아 당연히 시간 초과가 발생한다.)

그리고 어떠한 문자를 삭제하고 싶다면 다음 문자까지 그 사이에 존재하는 문자의 개수가 짝수여야 한다. 그래야 문자를 삭제할 수 있다.

이 방식을 통해서 문제를 해결할려 했는데 실패를 했다.
첫 제출에선 보니까 변수 자체를 잘못 업데이트 하며 틀렸다.

다른 체계

결국 입력받은 문자열, target 두개를 비교하면서 이동해야 하기 때문에 투포인터를 훨씬 더 눈에 잘 보이는 이름으로 지었다.

그리고 while문을 통해 이를 옮기는 방식을 사용했다. 그리고 틀렸다.
다른 사람들의 댓글에서 마지막에 남은 문자들의 개수를 확인해야 한다고 한다.
이거 이해하는데 한 30분 걸렸는데 다른 게 뭐가 있을까 계속 생각을 하다가 돌고 돌아 이게 제일 큰 문제였다.

삭제

위에 작성할 때 생각했었듯이 삭제를 하려면 짝수개가 남아야 한다.
그런데 문장에서 target은 만들었는데 남은게 홀수개가 남았으면 문장을 못 만드는 것이다. 모두 삭제를 할 수 없는거니까.

이를 추가하여 코드를 작성했다. 시간초과가 발생한다.
열심히 줄이고 조건을 걸고 해보려 했지만 안 된다. 그리고 이 때 확인을 하니 문자열의 길이 자체가 매우 길다. 앞에서 부터 모든 경우를 확인하려 한 완전탐색이기에 당연히 안 되는게 맞다...

타협

일단 문제는 맞추고 싶어서 다른 사람들의 풀이를 인용했다. 그리디 방식으로 제일 뒤에서 부터 체크를 하는 것이다.

이해가 안 된 부분이 있었는데 앞부분을 어떻게 삭제하냐 였다. 남은 문자를 생각했듯이 뭘 해야 하지 않나? 했지만 아니다.
앞에 남은 문자의 경우 계속 "Backspace"를 누르면 입력을 하지 않을 수 있다. 그래서 뒤에서 부터 체크를 할 때는 하나의 이점이 존재한다.
근데 이게 맞나 싶은 이유가 하나 있다.

그리디로 푸는 사람들의 경우 제일 뒤에서 동일한 문자가 나오면 이를 삭제하고 그냥 하길래 순서가 안 맞는 경우가 발생하면 예외가 발생하지 않을까 생각했다. 그러나 이러한 경우들을 원래 "NO"인 경우였다. 그냥 뒤에서 부터 온다면 공통 부분 문자열을 찾는다는 느낌으로 하면 된다. 앞에서부터 하려다가 시간이 좀 오래 걸린 거 같다..

다른 사람들은 보니까 반복문 1번으로 확인을 하네... 다시 봐야겠다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    data = sys.stdin.readline().rstrip()
    target = sys.stdin.readline().rstrip()
    data_idx, target_idx = len(data) - 1, len(target) - 1

    while data_idx >= 0 and target_idx >= 0:
        if data[data_idx] == target[target_idx]:
            data_idx -= 1
            target_idx -= 1
            continue

        data_idx -= 2

    print("YES" if target_idx == -1 else "NO")