[BOJ/백준] 12904 A와 B 파이썬

문제 링크 : https://www.acmicpc.net/problem/12904

12904번: A와 B

시작 문자열에서 조건에 맞게 A,B 문자 추가해서 목표 문자열까지 갈수 있냐 없냐 판별하는 문제이다.

처음에는 BFS로 접근했더니 메모리 초과가 났었다.

문자열이 엄청 많아지니까 초과가 날수밖에 없는 것 같다.

 

문제의 조건은 다음과 같다.

1. 문자열의 뒤에 A를 추가한다.

2. 문자열을 뒤집고 뒤에 B를 추가한다.

 

그래서 그리디하게 접근했다.

목표 문자 t에 끝이 A라면 1번 조건에 의해 추가 된 것이고, B라면 2번 조건에 의해 추가 된 것이다.

 

그래서 끝 문자가 A라면 끝 문자를 빼서 t에 다시 저장한다.

그게 아니라 B 라면 끝 문자열을 빼고 나머지를 뒤집어서 t에 다시 저장한다.

 

만약 t의 길이가 s의 길이와 같고 같은 문자열이라면 1을 출력 다르다면 0을 출력하고 나온다.

 

from sys import stdin

input = stdin.readline

s = input().strip()
t = input().strip()

def solv():
    global t
    while True:
        if len(s) == len(t):
            if s == t:
                print(1)
            else:
                print(0)
            return

        if t[-1] == 'A':
            t = t[:-1]
        else:
            t = t[:-1][::-1]
solv()