[Python] 백준 2812번 크게 만들기

문제

2812번: 크게 만들기

입력

• 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
• 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

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

입력 예제

4 2
1924

7 3
1231234

출력 예제

94

3234

문제 풀이

• 수를 가장 크게 만드려면 맨 왼쪽에 가장 큰 수가 와야하고, 배열을 사용하여 각 값에 접근하고 지우면 시간 초과가 날 수 있으므로 스택을 사용하여 해결한다.
• 숫자를 문자열 리스트로 저장한 후, 하나씩 꺼내보면서, stack에 값이 저장되어있고, 비교하는 값보다 스택에 있는 값이 적으며, 삭제 할 수 있는 횟수가 남아있다면 현 시점 스택의 제일 마지막 값을 삭제한 후, 더 큰 값을 넣는다.
• 마지막으로 출력되는 문자의 길이는 문자의 총 길이 n에서 k를 삭제한 길이가 되어야하므로, stack[n-k] 까지의 값을 출력한다

코드

n, k = map(int,input().split())
number = list(input())
stack = []
cnt = k
for num in number:
    while stack and num > stack[-1] and cnt > 0:
        stack.pop()
        cnt -= 1
    stack.append(num)

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