[Baekjoon] 12904번 : A와 B (Python, 문자열, 그리디)

[Baekjoon] 12904번 : A와 B (Python, 문자열, 그리디)

 

목차

 

 

 

 

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

12904번: A와 B

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 코드 길이 506B

 

s에 대하여 하나씩 추가하는 방향으로 진행했을 때 트리적으로 증가하고 이에 따라 시간 초과가 발생한다.

 

s = input()
t = input()

res = [s]
for i in range(len(t) - len(s)):
    tmp = []
    for j in range(len(res)):
        a = res[j] + 'A'
        b = res[j][::-1] + 'B'

        if len(a) == len(t):
            if a == t:
                tmp.append(a)
            if b == t:
                tmp.append(b)
            break

        if a in t or a[::-1] in t:
            tmp.append(a)
        if b in t or b[::-1] in t:
            tmp.append(b)
    res = tmp[:]

if len(res):
    print(1)
else:
    print(0)

 

 

방법 2 - 메모리 30840KB / 시간 68ms / 코드 길이 261B

 

방법 1에서는 하나씩 추가하는 방법을 채택했다면 본 방법은 하나씩 제거하는 방향으로 체크하는 것이다.

당연한 이야기겠지만 방법 1은 $2^n$으로 증가하는 반면 소거법은 빠르게 제거하므로 더 빠르고 메모리도 적게 사용한다.

 

s = input()
t = input()
res = 0
flag = False

while len(t) > len(s):
    if t[-1] == 'A':
        t = t[:-1]
    elif t[-1] == 'B':
        t = t[:-1]
        t = t[::-1]
    if s == t:
        flag = True
        break

if flag:
    print(1)
else:
    print(0)