[BaekJoon] 12904 A와 B (Gold 5) - 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

---

코드

 

처음에 bfs로 풀어봤다.

망.

시간초과 ㅋㅋ

그래서 아얘 반대로 풀었다.

S에서 T를 찾아가는것이 아니라 T에서 S를 찾아가는것으로 ....

그랬더니 풀렸돠.

 

연산이 두 가지 라서 가능했다.

 

1. 원래의 리스트 맨 뒤에 A추가

2. 원래의 리스트를 reverse한 뒤 맨 뒤에 B추가

 

코드.

import sys; input = sys.stdin.readline # 파이썬 입력을 빠르게 하기 위해서 input함수 재정의

S = list(input().strip()) # 맨 뒤의 줄바꿈 문자를 strip함수로 지우고 S에 리스트 형태로 저장
T = list(input().strip()) # 맨 뒤의 줄바꿈 문자를 strip함수로 지우고 T에 리스트 형태로 저장

while len(S) != len(T): # 두 리스트의 길이가 같아질 때 까지 반복한다
    if T[-1] == 'A': T.pop() # 만약 리스트 T의 맨 뒤의 글자가 A라면, 원래의 리스트에 A를 추가한 것 이라는 의미이므로 그냥 pop만 해준다
    else: # 그게 아니라면, B의 경우인데 이 경우 원래의 리스트를 뒤집은 뒤 맨 뒤에 B를 추가한 것 이라는 의미이므로 pop후에 리스트를 reverse해준다
        T.pop()
        T = T[::-1]

if S == T: print(1) # 만약 두 리스트의 값이 같다면 1을 출력하고
else: print(0) # 다르면 0을 출력한다

---

실행 화면

---

채점 결과