📚 2812 - 크게 만들기

크게 만들기

이해

N자리의 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하면 된다.

10 4
4177252841 → 775841

순서는 유지 시켜야한다.
이러한 문제를 풀 때는, stack을 이용하면 된다.

• 인덱스 앞 부분 삽입한다. +1씩 인덱스를 삽입 하다, stack에 삽입되어 있는 숫자보다 큰 숫자가 들어올 경우, stack을 정리한다. (k번 만큼)

4 1 → 7(정리) → 7 7 → 7 7 2 → 7 7 5(정리) → 7 7 5 2 → 7 7 5 8(정리) → 7 7 5 8 4 1

소스

import sys  
  
read = sys.stdin.readline  
  
n, k = map(int, read().split())  
number = list(read().rstrip())  
  
stack = []  
k_idx = k  
  
for in_num in number:  
    # k가 0보다 크고  
    # stack의 마지막 값이 현재 입력된 숫자보다 작을 경우  
    # pop  
    # 1 4 로 입력 될 때는 stack = [1] -> [4]    # 4 1 로 입력 될 때는 stack = [4, 1]    # 현재 값보다 작은 값들은 모두 제외 시킨다.  
    while k_idx > 0 and stack and stack[-1] < in_num:  
        stack.pop()  
        k_idx -= 1  
  
    stack.append(in_num)  
  
# 0 ~ n-k-1 까지 숫자가 가장 큰 수이다.  
print(''.join(stack[:n-k]))