[백준] 12904 A와 B | greedy? | Gol5 Python

[백준] 12904 A와 B | greedy? | Gol5 Python

https://www.acmicpc.net/problem/12904

 

접근

• 유형 : greedy

 

[문제 해석]

• 문자열을 두 종류의 연산만으로 특정 문자열로 바꿀 수 있는지 확인하는 문제
• 문자열 S, T주어짐. S를 T로 바꿀 것
• 가능한 연산 두가지    
  1. 마지막에 A추가
  2. 전체를 뒤집고 B추가
• 바꿀 수 있으면 1, 없으면 0 출력

 

구상

• 그냥 bfs로 연산 경우의 수 다 확인?? -> 너무 오래 걸림
• 거꾸로 연산? -> 이게 연산 수가 적다!
• T -> S 뒤집는 연산 - 현재 마지막 글자에 따라 연산이 결정된다.
  
  1. 마지막 글자가 A이면 : 마지막에 위치한 A제거
  2. 마지막 글자가 B이면 : 마지막에 위치한 B제거 후 전체 뒤집기

 

트러블 슈팅

• x

 

코드

import sys
input = sys.stdin.readline

S = input().strip()
T = input().strip()

while len(S) < len(T) :
    last = T[-1] #마지막 글자 없애기 전에 킵해두기
    T = T[:-1]

    if last == 'B' :
        T = T[::-1] #뒤집기

print(1 if S==T else 0)