백준 / 골드 3 / 2812 크게 만들기 / Python [스택]

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

구현 전 10분 구조화 방법은 정말 효과가 좋았다.

구조화

1. 시간복잡도 예상

N <= 500,000 : O(NlogN) 정도? 아무튼 O(N2)는 안됨. 조합? 완전탐색? 2^N급임
1,000,000,000

2. 요구사항 체크리스트화

그냥 잔뜩 써보면 감이 옴
이것처럼 뒤에꺼 비교해서 소급해야 하는 경우 주로 스택

3. 알고리즘 결정

4. 엣지 케이스 고안

첫 풀이

import sys
input = sys.stdin.readline

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

st = []

for s in str:
    while k > 0 and len(st) != 0 and int(st[-1]) < int(s):
        k -= 1
        st.pop()
    st.append(s)

while k > 0:
    st.pop()
    k -= 1

p = ''

for c in st:
   p += c
print(p)