[백준 12904] A와 B - python (solved.ac - 골드 5)

https://www.acmicpc.net/problem/12904

12904번: A와 B

풀이

문제를 보았을때 알수있는 힌트

단순하게 S를 T에 맞추어 풀면 틀리는 문제이다. 거꾸로 T를 S에 맞추면 쉽게 풀린다.

왜일까? 내가 생각하기로는 S의 문자열이 계속 커질텐데 계속해서 T를 확인하기위해 작업을 하면 무거워져 시간 초과가 나올수있다.

다음으로는 T의 문자열에서 오른쪽만 보며 A의 경우는 A만 빼주고 B인 경우에는 B를 빼준후 뒤집기만 하기에 S의 경우조건보다 2배로 빠르게 찾을 수 있다.

 

import sys
sys.setrecursionlimit(1000000)

def dfs(a,b,result):
    if len(a)==len(b):
        if a==b:
            result[0]+=1
    else:
        if b[-1]=="A":
            dfs(a,b[:-1],result)
        elif b[-1]=="B":
            temp=b[:-1]
            dfs(a,temp[::-1],result)

        

input = sys.stdin.readline

s= input().strip()
t= input().strip()
result=[0]
dfs(s,t,result)
if result[0]!=0:
    print(1)
else:
    print(0)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon12904.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리