[BOJ] 12904. A와 B(Python) / Greedy

12904번: A와 B

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램 작성하는 문제

• 사용 알고리즘 : Greedy(탐욕 알고리즘)
• 처음에 백트래킹 완전탐색으로 구현했는데 제출하자마자 시간초과 났다. 알고리즘 구분을 보니 Greedy 알고리즘이더라.
• 다른 사람의 풀이를 보고 무릎을 탁! 쳤다. 생각을 바꿔서 T에서 S로 만드는 것이다.
• 조건을 반대로 생각해 T의 마지막 문자가 "A"이면 pop, "B"이면 pop 하고 문자열을 뒤집는다.
• S와 T의 길이가 같아지면, 그 때 while문 탈출. 
• S와 T가 같다면 1, 다르다면 0을 출력한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

S = list(input().rstrip())
T = list(input().rstrip())

# T에서 S로 바꾼다고 생각하면 편함!
while len(S) != len(T):
    if T[-1] == "A":    # T의 마지막 문자가 "A"이면 pop
        T.pop()
    else:               # T의 마지막 문자가 "B" 이면 pop하고 뒤집기
        T.pop()
        T.reverse()

# 같으면 1 다르면 0 출력
if S == T:
    print(1)
else:
    print(0)

---

• 시간 : 104ms / 메모리 : 121220kb
• 고찰 : 생각의 전환이다. 생각을 뒤집으니 생각보다 간단한 코드로 그리디를 구현하고 pass까지 떠서 놀랐다.. ㅏ문제 풀 때 다양하게 사고해보자.