백준[1467] 수 지우기 (Python3)

생각보다 골 때리는 문제지만, 플2 치곤 약한 거 같다.
스택으로 풀면 쉽게 풀 수 있는데 왜 스택 태그가 없는지 의문

완전 탐색

입력된 N 자릿수를 지우는 모든 경우에 대해 구한다.
하지만 적당히 많은 수를 지우게 된다면 시간 초과를 받는다.
예를 들자면, N = 1000, 지워야 할 수가 300개이면 1000C300으로 시간 초과를 받는다.

완전 탐색 최적화

지우려는 수가 입력된 N의 맨 끝에 있을 수 있으니, N은 처음부터 끝까지 탐색해야 한다.
여기서 무엇을 출력할지, 무엇을 지울지 2가지를 기준으로 잡고 최적화를 할 수 있다.
나는 무엇을 출력할지에 대해 스택 자료구조를 가지고 다음 기준을 잡았다.

1. N의 각 자릿수와 지워야 할 수들에 대해 카운팅을 한다.
2. 스택의 상단과 현재 자릿수 n을 비교해 스택의 상단보다 작다면 카운팅 목록들을 참고해 스택을 pop 여부를 결정한다.
3. 만약 n의 카운팅과 지울 카운팅이 같다면 스택에 push 하지 않는다. 이때 카운팅을 조정해야 한다.
4. n의 카운팅을 1 줄이고 스택에 push 한다.

from collections import defaultdict, deque
N = input()
R = input()
nums, erase, answer = [], [], deque()
numCount, eraseCount = defaultdict(int), defaultdict(int)
for n in N:
    numCount[n] += 1
    nums.append(n)
for r in R:
    eraseCount[r] += 1
    erase.append(r)

for n in nums:
    if eraseCount[n] > 0 and eraseCount[n] == numCount[n]:
        numCount[n] -= 1
        eraseCount[n] -= 1
        continue
    while answer:
        top = answer[-1]
        if top >= n:
            break
        if eraseCount[top] == 0:
            break
        answer.pop()
        eraseCount[top] -= 1
    numCount[n] -= 1
    answer.append(n)
if eraseCount[answer[-1]] > 0:
    answer.pop()
print("".join(answer))