[백준 파이썬] 12919 A와 B 2

 

12919번: A와 B 2

문제

 

처음 제시된 문자열 S에 A를 더하거나 또는 B를 더한 후 뒤집는 과정을 반복해서 나중에 제시된 문자열 T로 만들 수 있는지 확인하는 문제이다.

---

 

풀이

처음에는 문제에 제시된 대로 S를 T로 만드는 코드를 작성해서 해결하려 했다. 하지만 시간초과가 나서 게시판을 확인해보니 S에서 T로 만드는게 아닌 T에서 S로 만들어야 한다는 글이 있었다.

 

따라서 T에서 S로 만드는 방법을 사용했다.

먼저 조건문을 만들어서 분기를 나누었다.

 

문자열에 가장 뒤에 A가 오는경우 

B + A = BA

AAB + A = AABA

이므로 A를 추가한 케이스이다.

 

문자열에 가장 앞에 B가 오는경우

BAB + B + reverse = BBAB

AAB + B + reverse = BBAA

와 같은 경우이므로 B를 추가한 후 뒤집은 케이스이다.

 

이를 이용해서 조건문을 만든다.

 

1. 문자열 S와 같은 경우 result값을 1로 바꾼 후 return한다.

 

2. 문자열에 가장 뒤에 A가 오는경우 A를 뺀 후 다시 check를 한다.

 

3. 문자열에 가장 앞에 B가 오는 경우 문자열을 뒤집고 B를 뺀 후 다시 check 한다.

이 때 BBA같은 경우는 BB + A의 경우도 가능하다. 하지만 2번에서 먼저 A를 체크해줬기 때문에 문제되지않는다.

 

이를 코드로 옮기면 다음과 같다.

def check(nT: list):
    global result
    if len(nT) == len(S):
        if nT == S:
            result = 1
        return
    
    if nT[-1] == 'A':
        nT.pop()
        check(nT)
        nT.append('A')
    
    if nT[0] == 'B':
        nT.reverse()
        nT.pop()
        check(nT)
        nT.append('B')
        nT.reverse()

 

 

 

 

코드

result = 0

S = list(input())
T = list(input())

def check(nT: list):
    global result
    if len(nT) == len(S):
        if nT == S:
            result = 1
        return
    
    if nT[-1] == 'A':
        nT.pop()
        check(nT)
        nT.append('A')
    
    if nT[0] == 'B':
        nT.reverse()
        nT.pop()
        check(nT)
        nT.append('B')
        nT.reverse()

check(T)
print(result)