가장 큰 수(스택)

가장 큰 수(스택)

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다)

 

만약 5276823 이 주어지고 3개의 자릿수를 제거한다면 7823이 가장 큰 숫자가 됩니다.

 

▣ 입력설명

첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제거해야할 자릿수의 개수가 주어집니다.

 

▣ 출력설명

가장 큰 수를 출력합니다.

 

▣ 입력예제 1

5276823 3

 

▣ 출력예제 1

7823

 

▣ 입력예제 2

9977252641 5

 

▣ 출력예제 2

99776

 

---

코드

n, m = map(int,input().split())
n = list(map(int, str(n))) # n을 한개씩 접근해서 int화 한 후 리스트화 한다.
stack = []

for x in n:
    # 스택이 비어있고, 더 뺄 숫자 카운트가 남아있고, 스택의 자료가 나보다 작을 때
    while stack and m>0 and stack[-1]<x:
        stack.pop()
        m-=1
    stack.append(x)

if m!=0: # m개의 숫자를 다 지우지 못했을 때, 그전에 끝났을 때
    stack = stack[:-m] # 뒤쪽 m개의 남은 자료 날린다.

res = ''.join(map(str, stack)) # stack을 str로 변환해준 다음 붙이기
print(res)

스택이 비어있을 때를 표현하는 법 : while stack

이렇게 하면 스택에 미리 숫자를 하나 넣고 시작하지 않아도 된다.

 

스택을 다 지우지 못했을 때, 스택 뒤쪽 남아있는 m의 갯수만큼 지워준다.