Baekjoon [12904] A와 B - python

 

문제 

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

12904번: A와 B

 

시간 초과난 코드 

# 규칙
# 1.문자열의 뒤에 A를 추가한다.
# 2.문자열을 뒤집고 뒤에 B를 추가한다.
import sys

sys.setrecursionlimit(10 ** 6)
s = input()
target = input()
cnt = len(target) - len(s)

def make_word(word):
    # print(word)
    if len(word) <= len(target):
        if word == target:
            return 1
        else:
            word_a = word + "A"
            result_a = make_word(word_a)
            reverse_word = word[::-1]
            reverse_word = reverse_word + "B"
            result_b = make_word(reverse_word)
            return result_a or result_b
    else:
        return 0
s = make_word(s)
print(s)

 

정답 코드

# 규칙
# 1.문자열의 뒤에 A를 추가한다.
# 2.문자열을 뒤집고 뒤에 B를 추가한다.
import sys

sys.setrecursionlimit(10 ** 6)
s = input()
target = input()
cnt = len(target) - len(s)


while(len(target)!= len(s)):
    if target[-1] == "A":
        target = target[:-1]
    elif target[-1] == "B":
        target = target[:-1]
        target = target[::-1]
if target == s:
    print(1)
else:
    print(0)

 

문제 접근

처음엔 단순히 재귀를 통해서 접근하는 방식을 접근했다. 이때 문자열 길이에 따라 시간초과가 발생했다. 이를 해결하고자 target_string에서 처음 string이 될때까지 반대로 접근했다. 이를 통해 시간효율성을 높여 시간초과를 해결했다.