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

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

1467번: 수 지우기

수 지우기 문제

N자리의 수에서 몇 개의 수를 지웠을 때 만들 수 있는 가장 큰 수를 구하는 문제

 

#사용 알고리즘

그리디

스택

 

📌문제 접근 포인트

1. 각 수를 지우기 위해서 일단 주어진 숫자(N)의 종류와 갯수,  지워야하는 숫자(R)의 종류와 갯수를 각각 카운팅 배열을 통해 구성해보자.

2. for문을 통해 N을 탐색하면서,  주어진 수가 존재하고, 지울 수 있는 숫자랑 갯수가 같으면 각각에서 줄여나가보자. (어차피 결국 전부 지워버림)
그렇지 않을 경우, 스택에 N에서 숫자를 가져와서 넣어보자. 이 때, 이미 스택이 존재하면,  스택의 마지막이 숫자를 지울 수 없거나, 현재 탐색중인 i보다 클 때 까지 스택의 마지막 숫자에 해당하는 것을 ecnt에서 지워버리면서 스택에서도 계속 빼주자.

3. 조건에 맞게 구현하면 성공!

⚙ 내가 푼 정답 코드

import sys
N = list(map(int, sys.stdin.readline().strip()))
R = map(int, sys.stdin.readline().strip())
result = []
ncnt = [0] * 10
ecnt = [0] * 10

for i in N: 
    ncnt[i] += 1

for i in R:
    ecnt[i] += 1

for i in N:
    if ecnt[i] and ecnt[i] == ncnt[i]:
        ncnt[i] -= 1
        ecnt[i] -= 1
    else :
        while result:
            if result[-1] >= i or not ecnt[result[-1]]:
                break
            ecnt[result[-1]] -= 1
            result.pop()
        ncnt[i] -= 1
        result.append(i)
print(*result, sep= "")