[백준] 12904. A와 B - Python

[Gold V]

 

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

12904번: A와 B

 

풀이

우선 두 가지 연산을 했을 때 어떤 일이 발생하는 지 생각하자.

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

이 연산은 단순하게 맨 뒤에 A를 추가할 뿐이다.

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

이 연산은 맨 앞에 B를 추가하고 뒤집는 것과 동일한 연산이다.

-> (이 때, 문자열을 뒤집는 것을 다르게 생각하면, 문자열은 그대로 두고 뒤에서부터 센다고 생각할 수 있다. 뒤집을 때마다 시작 index가 0이느냐, 맨 끝이느냐 하는 것만 달라진다는 것이다.)

---

이 두 가지를 생각하며, S를 T로 만들어 보며 생각했으나, 쉽사리 풀이가 생각나지 않았다.

그렇다면, 반대로 생각해 보자.

T를 S로 만드는 것이다.

그렇다면 두 가지 연산이 이렇게 변한다.

• 문자열의 맨 뒤에 있는 A를 지운다.
• 문자열의 맨 뒤에 있는 B를 지우고, 문자열을 뒤집는다.

원래의 두 가지 연산은 연산 시마다 두 가지 중 하나를 고를 수 있어 경우의 수가 기하급수적으로 증가했지만,

연산이 이렇게 변하므로, 문자열의 맨 뒤에 A가 있냐, B가 있냐에 따라 두 연산 중 하나를 선택하면 된다.

 

따라서 T 문자열을 맨 뒤에 있는 알파벳이 A인지, B인지에 따라 계속 길이를 줄여 나가면서, S 문자열과 길이가 동일해졌을 때 비교하면 된다.

S = input()
T = input()

isReversed = False

while len(S) != len(T):
    if isReversed:
        if T[0] == "A":
            T = T[1:]
        else:   # T[0] == "B"
            T = T[1:]
            isReversed = False
    else:
        if T[len(T)-1] == "A":
            T = T[:-1]
        else:   # T[len(T)] == "B"
            T = T[:-1]
            isReversed = True

def reverseResult():
    for i in range(len(T)-1, -1, -1):
        if T[i] != S[(len(T)-1)-i]:
            print(0)
            return
    print(1)
    
def result():
    for i in range(len(T)):
        if T[i] != S[i]:
            print(0)
            return
    print(1)
    
if isReversed:
    reverseResult()
else:
    result()