[Greedy] 12904번: A와 B

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

12904번: A와 B

 

1. 입력 예시

B

ABBA

 

2. 풀이

a. B를 ABBA로 만들어야 하지만 거꾸로 ABBA를 B로 만들 수 있는지 없는지 확인하면 쉽게 풀리는 문제다.

b. Target 문자열 맨 뒤에 A가 오면 단순히 A를 제거한다.

c. Target 문자열 맨 뒤에 B가 오면 B를 제거한 후 문자열을 뒤집는다.

d. 두 문자열의 길이가 같아질 때까지 반복한다.

 

3. 코드

from sys import *
  
# inputs
S = stdin.readline().rstrip()
# 문자열을 뒤집기위해 list로 입력을 받았다.
T = list(stdin.readline().rstrip())

# len(T)-1 ~ len(S) 순회
for i in range(len(T) - 1, len(S) - 1, -1):
    if T[i] == "A":
        # A가 오면 단순히 pop
        T.pop()
    elif T[i] == "B":
        # B가 오면 pop -> 뒤집기
        T.pop()
        T = T[::-1]

# 두 문자열이 같은지 확인
if "".join(T) == S:
    print(1)
else:
    print(0)

 

※ 문제 풀이가 복잡하거나 잘 안풀리면 거꾸로 생각하는 습관을 가지자.