백준(G3) 2812번: 크게 만들기(파이썬, Python3)

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

2812번: 크게 만들기

이 문제는 스택과 그리디 알고리즘을 섞은 문제다.

첫째 줄에 N과 K가 주어지고, 둘째 줄에는 N자리 숫자가 주어진다.

N자리 숫자에서 K개의 숫자를 지워서 가장 큰 수를 만드는 것이 이 문제다.

 

입력과 출력을 비교했을때 앞에 있는 작은 수들을 지워야 숫자가 커지는 것을 알 수가 있다.

나는 리스트를 하나 만들어서 숫자를 넣은 뒤, 뒤에 있는 숫자와 비교해서 더 작으면 제거하는 방식으로 접근했다.

코드와 함께 설명하겠다.

 

for n in mission_num:
    while stack and n > stack[-1] and mis > 0:
        stack.pop(-1)
        mis -= 1
    stack.append(n)

mission_num은 N자리 숫자다.

while 반복문을 이용해서 stack이 존재하고  n이 스택의 마지막 숫자보다 크고 mis(지우는 숫자의 개수)가 0보다 클 때 스택에서 맨 마지막 숫자를 제거하고 지우는 숫자의 개수를 관리하는 변수의 크기를 1 줄였다.

그리고 while문과 관계없이 stack에 n을 추가하도록 했다.

 

정답코드:

 

import sys
input = sys.stdin.readline
 
num,minus_num = map(int,input().split())
mission_num = list(input())
stack = []
mis = minus_num
for n in mission_num:
    while stack and n > stack[-1] and mis > 0:
        stack.pop(-1)
        mis -= 1
    stack.append(n)
print(''.join(stack[:num-minus_num]))