[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2812번 _ 크게 만들기

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

2812번: 크게 만들기

[문제]

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

[출력]

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

[아이디어]

1) 차례대로 스택에 쌓으면서 앞 자리보다 큰 수가 나오면 앞의 자리를 계속해서 pop해준다.

2) 다 쌓은 뒤 원하는 길이만큼만 출력한다. (원래 내림차순으로 정리된 경우 pop을 하지 않는 경우도 있을 수 있다.)

a,b = map(int,input().split())
k=a-b
s = []
for x in input():
    while s and s[-1]<x and b:
        s.pop()
        b -=1
    s.append(x)
print(''.join(s[:k]))