[백준/BOJ] gold5 - 12904번 A와 B (Python)

요즘 들어 굉장히 바쁜 날들을 살아오고 있다.
졸업 요건을 채우기 위해서 현장실습 인턴을 진행 중이고,
생각보다 주어진 업무가 많아서 쉴틈이 없다.
집에 오면 지쳐서 계속 쉬어서, 브론즈 문제만 풀면서 스트릭을 채웠다.
오랜만에 골드 문제도 풀었고 해서 블로그도 오랜만에 글을 써본다.

▶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을 출력한다.

728x90

▶풀이

처음에 bfs로 풀어봤다.

뭐를 넣고 추가하고 하는 문제는 bfs로 풀면 정답이 되는 경우가 많았기 때문이다.

하지만 visit를 위한 메모리를 따로 줘야 하고, 메모리 초과로 실패했다.

 

다시 간단한 풀이로 돌아와서 쉽게 풀어봤다.

그냥 주어진 t에 마지막 부분을 빼오면서 조건을 걸어줬다.

그렇게 하니까 가볍게 정답이 나왔다.

 

역시 문제는 쉬운 풀이부터 생각하고 풀어야 할 것 같다.

s = list(input())
t = list(input())

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

print(0)