[BOJ][🟡5][백준#12904] A와 B

문제 출처

BAEKJOON Online Judge #12904

문제

수빈이는 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

예제 2

입력

AB
ABB

출력

0

My Sol

from collections import deque

def main() :
    S = list(input())
    Q = deque(list(input()))
    D = {0:-1, -1:0}
    sl, ql = len(S), len(Q)
    i, op = 0, -1
    while i < ql-sl:
        i += 1
        p = Q.pop() if op else Q.popleft()
        if p == 'A': continue
        op = D[op]

    while Q:
        a = Q.pop() if op else Q.popleft()
        b = S.pop()
        if a!=b: return 0
    return 1

print(main())

컨셉은 현재 단어 T에서 맨 뒤의 알파벳에 따라 이전 문자가 결정이 된다는 것이다.

1. T의 길이에서 S의 길이를 뺀만큼 붙여준 알파벳을 떼어주어야 한다.
2. 입력을 받고, 각 길이를 계산해 그 길이 차이만큼 반복을 실시한다.
3. 뒤를 떼어내고 A/B 여부에 따라 앞의 문자열을 뒤집어주며 반복해도 되지만 불필요한 연산을 피하기 위해 떼어주는 위치를 앞과 뒤로 구분하기로 했다. 즉, B를 발견하면 뒤에서 떼고 있다면 앞에서 떼도록, 앞에서 떼고 있다면 뒤에서 떼도록 하는 것이다. 그 flag를 op로 두었다.
4. 이를 위해 deque를 사용한다. 앞에서 떼어내도, 뒤에서 떼어내도 모두 유리한 것이다.
5. 모든 반복을 종료하면 현재 reverse 여부를 지닌 op 변수와, 양쪽을 떼어낸 T(deque에 넣은 T를 Q로 두었다.)와 S가 남았다.
6. 이 T와 S의 상태가 같으면 1, 아니면 0이고 op 변수의 값에 따라 비교의 방향이 결정된다. 최초 -1로 둔 op 변수가 현재도 -1이면 정방향, 0이면 역방향으로 동일 여부를 확인한다.
7. 이 과정에 하나라도 동일하지 않다면 0을 반환하고, 모두 동일해 Q가 비게 된다면 1을 반환한다.
8. 이 반환값을 출력한다.

결과

맞았습니다!!

모범답안

출처

s = input()
t = input()
while len(t)!=len(s):
    if t[-1] == "A":
        t = t[:-1]
    else:
        t = t[:-1][::-1]
if s == t:
    print(1)
else:
    print(0)

연산시간이 2배는 빠른 풀이를 분석하려 한다….만 정말 어이가 없다. 내가 지양하려던 풀이이다. 매번 계산하며 뒤를 떼어내고 남아있는 T를 S와 비교하는 것이다.

아마도 문제의 입력이 최대 1,000으로 작아서 가능했던 풀이이고, 문제의 입력이 몹시 컸다면 메모리를 재할당하는 문제, 그리고 reverse하는 문제 등 시간, 공간 복잡도 관점에서 불리한 풀이가 될 것이다.