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

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

2812번: 크게 만들기

 

문제

 

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

 

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

 

출력

 

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

풀이

 

스택에 적절한 숫자를 하나씩 넣으면서 정답을 찾아가도록 한다.

처음에는 스택에 입력 받은 숫자의 첫 자리를 넣고, 입력 받은 숫자의 다음 자리 숫자들을 스택에 있는 값과 비교한다.

 

스택의 마지막 숫자와 입력 받은 숫자의 이번 자리를 비교한다.

만약 입력 받은 숫자의 이번 자리수가 스택의 마지막 숫자보다 작거나 같으면 해당 숫자를 단순히 스택에 추가하도록 한다.

만약 입력 받은 숫자의 이번 자리수가 스택의 마지막 숫자보다 크면 스택의 마지막 숫자를 꺼내고, 다시 스택의 마지막 숫자와 비교한다. 이 과정을 스택이 빌 때까지 반복하며, 스택의 마지막 숫자를 꺼내다 스택이 비게 된다면 해당 숫자(입력 받은 숫자의 이번 자리수)를 스택에 넣는다.

 

소스 코드

 

n, k = input().split()
n, k = int(n), int(k)

num = input()
ans = []
del_cnt = k
for i in range(n):
    while len(ans) > 0 and del_cnt > 0:
        if int(ans[-1]) < int(num[i]):
            ans.pop()
            del_cnt -= 1
        else:
            break
    ans.append(num[i])

ans = ''.join(ans)
print(ans[:n-k])