백준 12904 - A와 B

Sungwoo Hwang·2021년 3월 30일

백준 알고리즘 코딩테스트

우당탕탕 코테준비

목록 보기

3/6

문제 제목

12904번 A와 B

문제 설명

수빈이는 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을 출력한다.

예제 입출력

입력

B
ABBA

AB
ABB

출력

1
0

풀이

가장 먼저 생각난 풀이는 백트래킹을 사용해서 S가 T를 만드는 방법이였다. 매 노드에 대해서 뒤에 A를 뒤에 추가할지,뒤집어서 B를 뒤에 추가할지의 선택지 뿐이니 매우 간단할 것이라고 생각했지만, 첫 제출은 메모리 초과로 통과하지 못했다.

그 이유는 입력조건을 잘 보면 알 수 있다. T의 최대 길이가 1000이니 매 노드에서 선택지가 두가지 뿐이라고 해도 1000번째 단계의 탐색에서는 선택지가 무려 2^1000개에 달한다.
일반화했을때 T의 길이를 N이라 할때, 길이가 K(1<=K<=N)일때의 탐색일때 선택지는 2^K개에 달하니 당연히 메모리 초과가 발생할수 밖에 없었다.

문제의 분류가 그리디 알고리즘이어서 그 다음 떠올린 풀이는 주어진 S에 특정 조건에 따라서 A 혹은 B를 덧붙일지 고려하는것이였는데,(백준 2138번 전구와 스위치와 비슷한 풀이를 떠올렸다.) 이것도 문제가 생겼다.

A는 단순히 뒤에 덧붙이는 것이지만, B는 문자열을 뒤집은후 덧붙이는것이기 때문에 경우의 수가 매우 많았다.

문제를 최대한 단순하게 생각해서 바라보았다.

S에 여러 가지 적당한 연산을 해서 T가 되었다는 것은 T'에 한가지 연산을 해서 T가 되었다는 것과, T"에 한가지 연산을 해서 T' 이 되는 것이 같다는 것을 생각하게 되었다.

바꿔서 말하면 주어진 목표 문자인 T에 각 연산의 역원을 계속 수행하다 보면 S가 되는지 안 되는지 쉽게 알 수 있다는 것이다.

예를 들어서 위에서 언급한 연산의 역원은 아래와 같다.

문자열의 뒤에 A를 추가한다. -> 끝 문자열 하나를 삭제한다 (A 삭제)
문자열을 뒤집고 뒤에 B를 추가한다. -> 끝 문자열 하나를 삭제하고 뒤집는다.

그럼 어떤 연산의 역원을 수행할지만 판단하면 되는데 이건 판단하기 매우 쉽다. 단순하게 A로 끝나면 첫 번째 역원을, B로 끝나면 두 번째 역원을 수행하면 되는 것이다.

이렇게 연산의 역원을 계속 수행해서 T가 S와 길이가 같게 되었을때, S와 T의 일치여부만 판단해주면 되는것이다.

풀이코드

from sys import stdin

S = list(stdin.readline().rstrip('\n'))
T = list(stdin.readline().rstrip('\n'))

def sol():
  global S, T
  # 생각을 바꿔서 T에서 한단계씩 이전으로 되돌아가는것임
  # T의 마지막이 A라면 이전은 무조건 T[:len(T)-1]이고
  # T의 마지막이 B라면 이전은 T.pop() 후에 T[::-1]임
  # 이렇게 이전으로 계속 되돌아갔을때 S와 T가 일치하는지만 보면됨

  # ctrl-z를 해서 S로 되돌아갈수 잇느냐를 판단
  while len(S) != len(T):
    # T의 마지막이 A라면 
    if T[-1] == 'A':
      T=T[:len(T)-1]
    # T의 마지막이 B라면
    else:
      T.pop()
      T = T[::-1]

  if S == T:
    return 1
  else:
    return 0


print(sol())