문제

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

www.acmicpc.net/problem/2812

  • 입력

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

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

  • 출력

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

최종 코드

스택을 사용해서 푸는 문제였다.

N자리 숫자를 index 0부터 n-1까지 탐색하면서 pop과 append를 통해 답을 찾아간다.

pop을 하는 조건에는 3가지가 있다.

  1. stack[-1] < num[i] 스택의 마지막에 있는 숫자가 현재 숫자보다 작으면 pop한다.
  2. delCnt > 0 하지만 지우는 숫자의 개수가 k보다 커지면 안 되기 때문에 지운 숫자의 개수를 확인한다.
  3. stack 스택이 비어있으면 pop을 할 수 없으므로 확인한다.

출력 시에 스택에 n-k개 이상의 숫자가 들어가있을 수 있으므로 stack[:n-k]로 슬라이싱해서 출력한다.

import sys

n, k = map(int, sys.stdin.readline().split())
num = list(map(int, list(sys.stdin.readline().strip())))
stack = []
delCnt = k

for i in range(n):
    while delCnt > 0 and stack and stack[-1] < num[i]:
        stack.pop()
        delCnt -= 1
    stack.append(num[i])

print(*stack[:n-k], sep="")

참고 사이트