12. 백준 12904 (골드5) : A와 B _ python풀이

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1 복사

B
ABBA

예제 출력 1 복사

1

예제 입력 2 복사

AB
ABB

예제 출력 2 복사

0

---

*문제 해석

 이 문제는 '그리디 알고리즘' 문제다.

S에서 T로 넘어가는 것으로 하려면 따져야할 계산이 너무 많다. (바텀업 방식)

1. 문자열 뒤에 A추가

2. 문자열 뒤집고 B추가

그러나 거꾸로 계산하면 조건에 따라 정해진 계산을 해주면 된다. (탑다운 방식) T에 A가 추가됐다면 문자열에 큰 변동이 없던거고 B가 추가된거면 한번 reverse된 것이다. 따라서 T의 마지막요소인 T[-1]을 비교해 계산 후 S와 같은지 아닌지 확인하면 될 것이다.

 

*나의 코드

import sys

input = sys.stdin.readline

s= list(map(str, input().strip()))
t= list(map(str, input().strip()))

while len(s) != len(t):
    if t[-1] == 'A':
        t.pop()
    elif t[-1] == 'B':
        t.pop()
        t.reverse()

if s == t:
    print(1)
else:
    print(0)

 

*중요한 점

1. 바텀업 방식으로 풀기 어려운 문제는 탑다운 방식으로 쉽게 풀 수 있다.

2. 리스트의 [-1]요소는 그 리스트의 마지막 요소다.