[백준] 2812번 크게 만들기 (Python)

백준 2813 크게 만들기

숫자가 크고 요구하는 것이 단순해서 그리디알고리즘을 활용해야 한다는 것은 금방 알 수 있었지만, 구현하는 방식에서 틀려 시간 초과의 늪에서 헤맨 문제다. 문제의 포인트는 이러하다.

1. 앞의 수가 크다면 뒷 부분은 고려하지 않아도 된다.
2. 각각의 자릿수가 제일 큰 값이라면 해당 자릿수는 더 이상은 고려할 필요가 없기 때문에 그리디알고리즘이다.

이러한 특성을 토대로 만든 문제 솔루션은 이와 같다. 스택을 활용해 최댓값을 만드는 방법을 기억해두자.

1. 모든 자릿수(Loop 1)와 스택에 있는 수를 비교한다.
2. 해당 자릿수의 숫자보다 스택의 top에 있는 숫자가 작다면 해당 숫자는 제거되고 k에서 1을 뺀다.
3. 해당 자릿수의 숫자보다 스택의 top에 있는 숫자가 크거나 같다면, Loop 2를 종료한다.
4. 스택의 해당 자릿수의 숫자를 put 한다.
5. 마지막에 모든 숫자가 스택에 들어간 예외 케이스에는 꼬리를 자른다.

import sys

n, k = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().strip()
st = []

# Loop 1
for i in range(n):
    if k == 0:
        st.append(s[i:])
        break
    else:
    	# Loop 2
        while st and k > 0:
            if st[-1] < s[i]:
                st.pop()
                k -= 1
            else:
                break
        st.append(s[i])
print("".join(st) if k == 0 else "".join(st[:-k]))