[백준] A와 B

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

12904번: A와 B

그리디 알고리즘을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, A,B로만 된 영어단어 S와 T가 주어지는데, 

 

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

2. 문자열을 뒤집고 뒤에 B를 추가한다. (뒤집는 것의 의미는 ABBABA면 ABABBA로 뒤지는 것임)

 

이렇게 두 방법을 이용해 

S를 T로 바꿀수 있다면 1을 없다면 0을 출력해야 합니다.

 

<Solution>

T에서 S로 거꾸로 진행을 하면 됩니다.

 

T가 만약 A로 끝난다면 1번의 "문자열의 뒤에 A를 추가한다"의 연산이 이전에 일어난 것이므로 반대로 A를 떼어내 주고, 

T가 만약 B로 끝난다면 2번의 "문자열을 뒤집고 뒤에 B를 추가한다"의 연산이 이전에 일어난 것이므로 반대로 B를 떼어내 주고, 문자열을 다시 뒤집어 주면 됩니다.

 

이렇게 while loop를 돌리다 S가 나오거나, 문자열이 전부 제거되었음에도 A가 나올 수 없다면, return을 올바르게 하도록 구현하면 됩니다.

 

실제 구현은 아래와 같습니다. 

import sys

S = list(sys.stdin.readline().rstrip())
T = list(sys.stdin.readline().rstrip())

# T->S
while(1):
    if T == S:
        print(1)
        break
    if len(T) == 0:
        print(0)
        break
    if T[-1] == 'B':
        T.pop()
        T = T[::-1]
    else:
        T.pop()