[PS] BOJ 2812 / 크게 만들기

문제 링크: https://www.acmicpc.net/problem/2812

풀이

초안

처음에는 0~9의 각 숫자별로 어느 위치(인덱스)에 있었는지 기록한 뒤, 0부터 차례대로 제거해 나가는 방식으로 구현했습니다. 그러나, 이 방식은 $K$개의 숫자를 제거한 뒤의 숫자를 다시 구성하는 과정에 어려움이 있어 다른 방식을 생각해보게 되었습니다.

큰 수가 앞에 오게 지우기

$N$ 자리의 수에서 $K$개의 숫자를 지워낼 때, 기존의 순서를 유지하면서 수를 크게 만들 방법을 찾아야 합니다. 아래의 예제 데이터를 통해 생각해봅시다.

7 3
1231234

7자리의 수에서 3개의 숫자를 지워야 합니다. 먼저 조건에 맞게 답을 생각해보면, 3234가 최선의 답임을 알 수 있습니다.
이제 숫자를 어떤 방법으로 지워야 3234라는 답을 얻을 수 있을지 고민해봅시다.

먼저, 기존 수의 앞에서부터 숫자를 하나씩 스택에 쌓습니다.
이 때, 스택의 가장 위에 저장된 원소와 새로 스택에 넣을 숫자를 비교했을 때 스택의 숫자가 더 작다면 이를 제거합니다. (항상 큰 수가 더 앞에 위치하도록 조절합니다.)

이 과정을 숫자를 계속 읽어가며 $K$개의 수를 모두 지울 때 까지 반복합니다.

이 때, 위 방식으로 수를 지웠을 때 $K$개의 수가 모두 지워지지 않는 경우가 있습니다.
(항상 스택에 넣은 이전 수보다 다음 수가 더 작은 경우)

이 경우, 완성된 숫자의 뒤에서부터 남은 개수만큼 지운 뒤 답으로 사용하면 됩니다.
이는 항상 큰 수가 앞으로 오게 지웠기 때문에, 뒷 자리에 상대적으로 작은 숫자들이 위치하기 때문입니다.

전체 코드

from collections import deque

input = open(0).readline

N, K = map(int, input().split())
number = input().rstrip()

stack = deque()
cur = 0
while cur < N:
    while K > 0 and stack and stack[-1] < number[cur]:
        stack.pop()
        K -= 1
    
    stack.append(number[cur])
    cur += 1

while K > 0: # 앞에서 K보다 덜 지웠을 경우, 끝에서 남은 개수만큼 지워낸다.
    stack.pop()
    K -= 1

print("".join(stack))