[백준 2812] 크게 만들기

문제

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

 

입력

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

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

 

출력

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

---

접근

순서대로 탐색을 진행하여 특정한 조건에 따라 선택한 숫자는 스택에 push한다.

이후 스택의 top과 현재 숫자를 비교하는데 앞으로 선택해야할 개수보다 남아있는 수가 작을 때까지 크기를 비교한다.

선택해야할 개수보다 남아있는 수가 크다면 계속해서 스택의 top과 비교하여 현재 값이 크다면 교체를 해준다.

 

구현

- 문자열의 형태로 숫자를 입력받아 numbers에 저장하였다.

- 이제 숫자를 하나씩 꺼내어 로직을 구현한다.

- 스택이 비어있다면 현재 꺼낸 수를 스택에 push한다.

- 스택 내에 숫자가 존재한다면

- 스택의 top보다 현재 수인 number가 크고 선택해야할 숫자보다 남아있는 수가 크거나 같다면 스택을 pop한다.

- while문이 종료되고 스택의 길이가 N-K 미만일 때만 현재 숫자인 number를 push한다.

- N-K미만이라는 것은 아직 선택해야할 숫자가 남아있다는 뜻이다.

for idx in range(len(numbers)-1):
    number = numbers[idx]
    if stack:
        while stack and stack[-1] < number and (N-K-len(stack)) <= N - idx - 1:
            stack.pop()
        if len(stack) < N - K:
            stack.append(number)
    else:
        stack.append(number)

---

전체 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
numbers = input()

stack = []
for idx in range(len(numbers)-1):
    number = numbers[idx]
    if stack:
        while stack and stack[-1] < number and (N-K-len(stack)) <= N - idx - 1:
            stack.pop()
        if len(stack) < N - K:
            stack.append(number)
    else:
        stack.append(number)

print(''.join(stack))