[백준] 2812번 - 크게 만들기 Python

문제

---

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

입력

---

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

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

출력

---

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

예제 입력 1

---

4 2
1924

예제 출력 1

---

94

나머지 예제는 생략한다.

풀이

---

Python

import sys
input = sys.stdin.readline

n,k = map(int,input().rstrip().split())
nums = list(map(int,input().rstrip()))
answer = []

cnt = k
for i in range(n):
    while cnt>0 and answer:
        if answer[-1] < nums[i]:
            answer.pop()
            cnt-=1
        else:
            break
    answer.append(nums[i])

print(''.join(map(str,answer[:n-k])))

정리

---

• 스택에 숫자를 넣으면서 현재 넣고자 하는 값이 스택의 상단 값보다 크면 스택에서 값을 하나 제거하고, 스택이 비거나 큰 값이 나올때까지 반복한다.