백준 2812 크게 만들기(python)

문제

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

2812번: 크게 만들기

---

스택을 사용하여 푸는 문제였습니다. 접근 방식이 히스토그램에서 가장 큰 사각형 만들기 문제를 스택으로 풀 때 와 비슷해서 정리해 보았습니다. 이 문제도 모노톤 스택 형태 내림차순으로 만들어 줍니다. 

절차는 다음과 같습니다.

• 주어진 숫자를 문자열로 형태로 처음 부터 순회하면서 스택에 넣어줍니다
• 스택에서 pop 하는 조건은 스택의 top 값 보다 현재 순회하는 위치의 값이 더 크다면 st을 pop 해주고 현재 값을 넣어 줍니다. 
• pop 할때 문제의 조건으로 주어진 지울 수 있는 숫자의 개수를 하나씩 줄여줍니다.
• 최종적으로 모든 문자열을 순회한 뒤 K 값이 남아 있다면 남은 만큼의 숫자만 제외하고 스택의 가장 밑에서부터 출력해 줍니다.

---

소스코드 

import sys
input = sys.stdin.readline


N, K = map(int, input().rstrip().split())


num = input().rstrip()
st = []

for i in num:
    while len(st) != 0 and st[-1] < i and K > 0:
        st.pop()
        K -= 1
    st.append(i)

ans = []

if K > 0:
    for i in range(len(st)-K):
        ans.append(st[i])
else:
    for i in st:
        ans.append(i)


print("".join(ans))