백준 2812번: 크게 만들기 (G3) - Python 풀이

문제 설명

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

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

입력

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

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

출력

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

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

풀이 과정

역시 골3.
나름대로 논리 세워서 풀었는데 계속 시간 초과가 났습니다.
제 방법에서는 시간을 더 줄일 수가 없었는데요.
결국 아이디어 싸움입니다.

N개 중에 K개를 삭제해야 합니다.
이때, 앞에 있는 수가 뒤에 있는 수보다 작으면 삭제해야 합니다!!!!!!
이를 위해 스택을 사용합니다.

정답 코드

# 빠른 입력
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
numbers = list(map(int, input().strip()))
tmp = K
stack = []

# 왼쪽부터 숫자 하나씩 확인
for number in numbers:
    # 스택과 지울 숫자가 남았고, 앞의 수가 뒤의 수보다 작을 때
    while stack and tmp > 0 and stack[-1] < number:
        # 스택의 top 제거
        stack.pop()
        # 지워야 하는 숫자의 개수 1 감소
        tmp -= 1
    # 숫자 확인할 때마다 스택에 push
    stack.append(number)
    
# 반복문 다 돌았는데도 스택 길이가 N-K이 아니라면
# 뒷자리 K개 삭제
answer = stack[:N-K]

print(''.join(map(str, answer)))

 

이상입니다.