🥇 2812 크게 만들기
문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
분석
그리디 알고리즘에 스택을 사용하여 풀 수 있는 문제이다. 처음에는 stack의 모든 요소들을 출력하게 하였으나,
7 5
9929191 같은 경우 앞의 99가 정답이고 뒤 29191은 스택에 계속 push()된다. 따라서 k개의 원소를 다 지우지 못했기 때문에 출력범위를 수정하였다.
예제를 살펴보면, 1924에서 2개를 지워야 할 때,
- 스택이 비어있거나 더이상 지울 수 있는 수가 없거나 top보다 작거나 같은 경우 : 스택에 push()
- 스택의 top보다 큰 값이고 아직 더 지울 수 있다면 : 스택에서 pop()
- 아직 k개를 못지운 케이스가 있으므로 출력할 때에는 0부터 len(stack) - k까지 출력할 수 있도록 한다.
소스 코드
import sys
input = sys.stdin.readline
# n자리 숫자, k개의 숫자를 지움
n, k = map(int, input().split())
number = list(map(int, input().strip()))
stack = []
for i in range(n):
# stack top보다 큰 값이 들어오면 pop()
while k and stack and stack[-1] < number[i]:
stack.pop()
k -= 1
stack.append(number[i])
# 위에서 k개를 다 못지운 경우가 있으므로 -k를 추가
for i in range(len(stack) - k):
print(stack[i], end="")