[BOJ 2812, Python 3] 크게 만들기

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

2812번: 크게 만들기

 

풀이

일단 반폐구간 [0, k)에서 얻을 수 있는 최댓값과 해당 인덱스를 구합니다. 그 인덱스를 x라고 하면 이후 (x, x+k]에서도 최댓값과 해당 인덱스를 구하는 과정을 반복합니다.

이게 가장 주먹구구식 방법인데 해당 방법을 사용하면  N = 500000, K = N-1일 때 생각하면 시간초과가 나옵니다.

 

해당 방법과 결과가 똑같은데 시간이 좀 더 빠른 방법을 생각해보면 원소를 스택에 넣어주는데, 넣어주기 전에 while문을 이용해 해당 원소의 값보다 스택 맨 위에 있는 값이 작으면 해당 값을 뺴주는 것입니다.

 

이렇게 하면 K번 문자를 삭제할 떄까지 스택에 있는 숫자들이 단조감소함이 보장됨을 알 수 있습니다.

왜냐하면 만약 스택의 맨 위 값보다 큰 값이 들어오면 해당 원소보다 큰 값이 나오기 전까지 스택에 있는 원소를 모두 빼주기 때문에 이것도 단조감소가 되고, 반대의 상황이라면 스택 원소로 들어가서 단조감소가 되서 어떻게 되든 무조건 단조감소가 될 수 밖에 없습니다.

 

만약 K번을 다 사용하지 못했으면 마지막 남은 횟수만큼 뒤에 있는 숫자들을 제거하고 출력해주면 됩니다.

 

 

코드

n, k = map(int, input().split())
s = [*map(int, [*input()])]
q = []
for i in range(n):
    while k and q and q[-1] < s[i]:
        q.pop()
        k -= 1
    q.append(s[i])
print(''.join(map(str, q[:len(q)-k])))