파이썬 알고리즘 218번 | [백준 10942번] A와 B - 그리디

218. A와 B

1) 어떤 전략(알고리즘)으로 해결?

• 그리디

2) 코딩 설명

<내 풀이>

import sys
sys.setrecursionlimit(10**5)
n = (sys.stdin.readline().strip())
target = list(sys.stdin.readline().strip())
candid = []

def recur(num, candidate) :
    if num==len(n) :
        candid.append("".join(candidate))
        return
    
    else :
        if candidate[-1]=='A' : 
            candidate.pop()

        elif candidate[-1]=='B' :
            candidate.pop()
            candidate = list(reversed(candidate))
        recur(num-1, candidate)

recur(len(target), target)

if n in candid : print(1)
else : print(0)

<내 틀렸던 풀이, 문제점>

import sys
sys.setrecursionlimit(10**5)
n = (sys.stdin.readline().strip())
target = list(sys.stdin.readline().strip())
candid = []

def recur(num, candidate) :
    #print(num,candidate)
    if num==len(n) :
        candid.append("".join(candidate))
        return
    
    else :
        if candidate[-1]=='A' : 
            candidate.pop()

        elif candidate[-1]=='B' :
            candidate.pop()
            candidate.sort(reverse=True) 
            # 이 부분에서 역순 정렬이 안먹히구 있었음 
        else : return
        recur(num-1, candidate)

recur(len(target), target)
#print(candid)

if n in candid : print(1)
else : print(0)

• 역순 정렬이 안먹히구 있었다!

<반성 점>

• 역순 정렬 체크
  단순히 그리고 reversed 아니고 이 reversed 를 list로 지정해줘야 list에 역순정렬최종저장이 되지

<배운 점>

• 그리디의 새로운 개념 습득을 했지 뭐야