[python] 백준 12904번: A와 B(Greedy)

#  12904 A와 B

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

12904번: A와 B

⭐ 코드

import sys
input = sys.stdin.readline
S = list(map(str, input().strip()))
T = list(map(str, input().strip()))

while len(S) != len(T):
    
    if T[-1] == 'A':
        T.pop()
    elif T[-1] == 'B':
        T.pop()
        T.reverse()

if S == T:
    print(1)
else:
    print(0)

📝 풀이

처음에는 S에서 T를 만드려고 고민했었다. 바텀업 방식으로 문제를 접근하게 되면

1. 문자열 뒤에 A를 추가

2. 문자열 뒤집고 B를 추가

위의 두 조건을 계속해서 판단해줘야 한다. 접근법이 잘 떠오르지 않아서 구글링을 해보니 탑다운으로 문제를 해결하면 훨씬 쉽다는걸 알게 됐다.

 

핵심 포인트는 다음과 같다.

T에 마지막 문자열이 B라는 것은 문자열을 한번 뒤집었다는 뜻이다. T의 마지막 문자열이 A라는 것은 A를 추가했다는 뜻이다. 이 두가지 경우만 생각한다면 쉽게 코드를 작성할 수 있다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline
S = list(map(str, input().strip()))
T = list(map(str, input().strip()))

while len(S) != len(T): # 1번
    
    if T[-1] == 'A': # 2번
        T.pop()
    elif T[-1] == 'B': # 3번
        T.pop()
        T.reverse()

if S == T: # 4번
    print(1)
else:
    print(0)

문제의 조건을 다시 살펴보면 다음과 같다.

1. 문자열 뒤에 A를 추가

2. 문자열 뒤집고 B를 추가

 

이를 반대로 생각해보면

1. A를 추가했다면 문자열 변화가 없음

2. B를 추가했다면 문자열을 뒤집었다는 뜻임

 

# 1번

S와 T가 같은지 확인하는 문제이므로 각 리스트의 길이가 같을때까지 while문을 실행시켜준다.

 

# 2번

T의 마지막요소인 T[-1]가 A라면 S를 만들기 위해 추가한 A를 빼준다.

 

# 3번

T의 마지막요소인 T[-1]가 B라면 문자열을 뒤집었다는 뜻이므로 B를 빼주고 문자열을 뒤집어준다.

 

# 4번

S와 T의 길이가 같아지면 while문을 탈출하고 S와T가 같다면 print(1), 아니라면 print(0)을 해준다.