https://www.acmicpc.net/problem/2812
시간 1초, 메모리 128MB
input :
- N, K(1 ≤ K < N ≤ 500,000)
- N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
output :
- K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력
너무 만만하게 생각했다.
당연히 문자열의 순서를 유지하면서 간다는 것을 생각해야 했는데 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
일단 지우는 횟수는 k번이다. 그 후부터는 그대로 문자열이 유지 될 것이다.
그렇다면 어떤 수들을 지워야 할까?
앞에 저장되어 있던 수가 지금 저장되려는 수보다 작은 경우 삭제를 하면 된다.
그래서 temp라는 배열을 통해 계속 저장을 하게 하자.
그러고 나면 temp의 길이는 n - k 일 수도 있지만, 이 보다 길 수도 있다. 그러나 문제가 원하는 것은 n - k 까지의 숫자니까 슬라이싱을 해서, 출력해주자
import sys
n, k = map(int, sys.stdin.readline().split())
data = list(sys.stdin.readline().strip())
temp, cnt = [], k
for i in range(n):
# 문자열에서 삭제할 것은 k번이니까 그만큼 while문에 걸리게 됨.
# 답으로 가지고 가는 배열이 temp니까 temp가 존재하고,
# 새로 들어올 문자가 이전에 존재하던거 보다 클 때, 답이 된다.
while cnt > 0 and len(temp) > 0 and temp[-1] < data[i]:
temp.pop()
cnt -= 1
# 그리고 삭제할 것들을 다 지우면 다른 문자열들이 계속 입력된다.
temp.append(data[i])
ans = "".join(temp[:n - k])
print(ans)
