💡 문제
수빈이는 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을 출력한다.
💭 접근
처음 이 문제를 접했을 때는 백트래킹을 이용하여 s에서 t로 가는 방식으로 문제를 해결하려 했으나 시간초과, 메모리초과가 계속 발생하였다. 그러던 와중, t의 끝 알파벳에 따라 적용할 수 있는 연산이 정해져 있다는 것을 알게 되었고, s에서 t로 가는 것이 아닌 t에서 s로 반대로 가야한다는 것을 깨달았다.
그리하여 그리디하게 t의 마지막 알파벳이 A라면, 마지막 A만 빼주고 t의 마지막 알파벳이 B라면 마지막 B를 빼준 후, 문자열을 뒤집는 방식으로 구현하였다. 이후 t와 s의 길이가 같을 때 서로 문자열이 같다면 1을, 다르다면 0을 출력해주면 된다.
📒 코드
s = list(input())
t = list(input())
while len(t) >= len(s):
if t[-1] == 'A':
t.pop()
elif t[-1] == 'B':
t.pop()
t = t[::-1]
if t == s:
print(1)
break
else:
print(0)💭 후기
이때까지 문제를 풀면서 거꾸로 거슬러 올라가는 방식으로 해결한 문제가 없었던 것같은데 매우 신선했던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/12904
