[백준]2812 크게만들기 #그리디#스택

1. 풀이

(1) 전체 문자열을 N번반복

(2) 전체 문자열의 i번째 반복때(i번째 숫자일때) 아래와 같은경우가 나올때까지 스택에서 숫자를 뽑음

  ① 스택에 숫자가 없는경우

  ② 스택에서 뽑은 숫자가 i번째 숫자보다 크거나 같을때

  ③ 지울수 있는 횟수를 다 썼을때

(3) 최종적으로 나온 stack에서 왼쪽부터 N-K개까지의 숫자가 답이됨.

​

2. 소스코드

from collections import deque

N,K=map(int,input().split())
num=input()
size=len(num)

cut=0

stack=deque([num[0]])
isFull=False
for i in range(1,size):
    intI=int(num[i])
    # 1. 스택에 숫자가 없으면 그만
    while(stack):
        stackNum=stack.pop()
        # 2. 스택에서 뽑은 숫자가 i번째 숫자보다 크거나 같을때
        if int(stackNum)>=intI:
            stack.append(stackNum)
            break
        cut+=1
        # 3. 지울 수 있는 횟수를 다 썼을때
        if cut==K:
            isFull=True
            break

    if isFull:
        stack.extend(num[i:])
        break
    else:
        stack.append(num[i])


ans="0"+"".join(list(stack)[:N-K])
print(int(ans))