[백준] 2812번 크게 만들기 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/2812

문제

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

문제해결 아이디어

• 숫자의 맨앞자리부터 순회하면서 스택에 넣고 다음숫자와 비교하면서 더큰수가 앞에 올수 있도록 조정한다.

소스코드

import sys

n,k = map(int, input().split())

num = input().strip()

stack = []

for i in num:
  while stack and stack[-1] < i and k > 0: #스택이 존재하거나 스택의 마지막 숫자가 현재 순회하는 숫자보다 작을떄 까지 and k로 횟수제한 체크
    stack.pop()
    k -= 1
  stack.append(i)

if k > 0: #다 순회했는데도 횟수가 남은경우 ex) 987654 그냥 슬라이싱
  print("".join(stack[:-k]))
else :
  print("".join(stack))