[파이썬] 백준 2812번: 크게 만들기 (그리디 알고리즘)

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

문제

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

입력

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

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

출력

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

예제 입력 1 복사

4 2
1924

예제 출력 1 복사

94

 

## 그리디 알고리즘
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
arr=input().strip() # strip: 양쪽 공백 삭제
deleted=0 # 현재까지 삭제횟수
stack=[] # 스택
for x in arr:
    # 스택이 비어있지않고 현재 원소가 스택의 top()보다 크면
    while len(stack)>0 and stack[-1]<x:
        # 더이상 삭제못하면 break
        if deleted == k:
            break
        # 스택에서 pop() 수행(제일 큰숫자로 만들기위해)
        else:
            stack.pop()
            deleted+=1
    stack.append(x)
    
# 삭제 횟수가 남아있다면 다 없어질때까지 pop()
for i in range(k-deleted):
    stack.pop()
    
print(''.join(stack))