[ 2812 ] [ Stack ] 크게 만들기

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

2812번: 크게 만들기

 

---

풀이 과정

---

1. 숫자 K개를 지워서 얻을수 있는 가장 큰 수를 구하려면.. 첫자리를 가장 크게, 두번째 자리를 그다음 크게, ... 진행하여야 한다.
2. 따라서 스택으로 풀이를 하면 된다.
   1. 왼쪽 자리에서부터 오른쪽 자리 순서로 스택에 넣는다.
   2. 스택에 넣을 때, 기존 스택의 맨 위 숫자보다 현재 숫자가 크다면 해당 숫자를 빼내준다.
   3. 숫자를 빼낸 횟수가 K개라면 (2)는 생략한다.
3. 전체 자리에 대해 진행이 되었다면, 마지막으로 K개보다 숫자를 덜 빼냈을수도 있을 것이다.
4. 따라서, K개가 될때까지 스택에서 pop해주면 된당.

---

소스 코드

---

 

import sys

input = lambda : sys.stdin.readline().rstrip()

N, K = map(int, input().split())
number = list(map(int, list(input())))
stack = []
delete_count = 0

for n in number:
    while stack and n > stack[-1] and delete_count < K:
        stack.pop()
        delete_count += 1
    stack.append(n)

if delete_count < K:
    for _ in range(K-delete_count):
        stack.pop()

if len(stack) == 0:
    print(0)
else:
    print("".join(map(str, stack)))