[알고리즘] BOJ 2812 크게 만들기

[BOJ] 2812 크게 만들기 바로가기

📍 문제

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

📍 입력

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

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

📍 출력

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

📍 풀이

✍ 코드

from sys import stdin
N,K = map(int,stdin.readline().split())
numbers = list(map(int,stdin.readline().strip()))
result = []
k = K # 현재 삭제할 원소의 갯수
for i in range(N):
  # 현재 삭제할 원소의 갯수 값이 0이 아니거나
  # result 리스트가 비어 있지 않거나
  # result 리스트의 마지막 값이 현재 numbers 리스트의 원소 값 보다 작다면
  while k and result and result[-1] < numbers[i]:
    result.pop() # result 마지막 원소 제거
    k-=1 # 현재 삭제할 원소의 갯수 값 -= 1
  result.append(numbers[i]) # 현재 원소 값 result에 추가
for i in range(N-K):
  print(result[i],end='')