[Python] boj no. 2812 : 크게 만들기

Problem

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

Idea

같은 자리의 두 값을 비교했을 때 더 큰 값은 높은 자리 수부터 비교해 더 큰 수를 가지는 값이다. 따라서 N자리 숫자에서 숫자 K개를 지워 가장 높은 값을 얻기 위해서는 어떻게 하면 높은 자리 수부터 최대한 내림차순인 값을 만들 수 있는가에 달려있다.

숫자를 지우는 수의 제한이 없다고 했을 때, 두 번째 자리의 수부터 자신의 왼쪽 자리 수와 비교하여 자신이 크면 왼쪽 자리의 수를 지우는 방식으로 오름차순의 숫자를 얻을 수 있다. 하지만 문제에서는 지워야 하는 횟수가 정해져 있으므로 다음과 같은 기준으로 숫자를 지워야 한다.

1. 왼쪽에서 두 번째 숫자부터 탐색을 시작한다.
2. 삭제 횟수가 남아있는 동안, 기준 숫자보다 왼쪽의 숫자가 클 때까지 왼쪽의 숫자를 제거한다.
3. 삭제 횟수가 0이 되면 삭제 연산을 실행하지 않는다.
4. 모든 숫자를 탐색했음에도 불구하고 삭제 횟수가 남아있다면 오른쪽 자리부터 삭제 횟수만큼 숫자를 제거한다.

스택을 활용하여 위의 기준을 통한 탐색을 구현했다.

Code

from collections import deque

N, K = map(int, input().split())
numbers = list(map(int, input().rstrip()))
stack = deque()

for num in numbers:
    while stack:
        if K > 0 and num > stack[len(stack)-1]:
            stack.pop()
            K -= 1
        else:
            break
        
    stack.append(num)
    
stack = list(stack)
print(*stack[:len(stack)-K], sep='')

Comment