[python] 백준 2812 크게 만들기

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

2812번: 크게 만들기

문제 해결

• stack을 쌓아서 앞쪽에 큰수들로 이루어지도록 하는 것이 포인트
• 특이 케이스로 같은 숫자가 계속 나와서(예: 33333) 제거하기 애매한 상황이 나올 수 있음
• 따라서 stack이 많이 쌓일 수도 있으므로 앞에서부터 n-k개를 출력해야한다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque
n, k = map(int, input().split())
que = deque([int(c) for c in str(input().rstrip())])
A = []
A.append(que.popleft())
cnt = 0
while que:
    x = que.popleft()
    while cnt<k and len(A)>0:
        if A[-1] < x:
            A.pop()
            cnt +=1
            continue
        break
    A.append(x)
ans = ''.join(map(str,A[:n-k]))
print(int(ans))