$O(n)$
주어진 길이 n의 문자열을 str
구한 답을 a[1],a[2], ...,a[n-k] 이라고 하자.
잘 생각해보면
a[1]=max(str[b1]) (0<=b1<=k)
a[2]=max(str[b2]) (b1<b2<=k+1)
...
a[n-k]=max(str[bn-k]) (bn-k-1<bn-k<n)
간단하게 큐 자료구조를 이용하여 O(n)에 a[]를 구할 수 있다.
#include<stdio.h> #include<queue> using namespace std; int n, k; char str[500001]; deque<char> q; void push(char x) { while (!q.empty() && q.back()<x) q.pop_back(); q.push_back(x); } int main() { scanf("%d %d %s", &n, &k, str); for (int i = 0; i<k; i++) push(str[i]); for (int i = k; i<n; i++) { push(str[i]); printf("%c", q.front()); q.pop_front(); } return 0; }
안녕하세요. 블로그 보고 도움 많이 받고 갑니다. 다름이 아니라,
답글삭제혹시 풀이에서 0 ~ K-1까지는 push만 하고,
K부터 ~ n-1까지는 push와 print를 같이 하는데
이렇게 구조를 잡은 이유가 있을까요??? 잘 와닿지가 않아서요.
답을 높은 자리부터 한 자리씩 구한다고 합시다.
삭제답의 가장 높은 자리에 오는 수는 주어진 n 개의 수 중 가장 앞 k+1개의 수 중 최댓값이 됩니다. (그러한 수가 여러 개 있다면 앞의 수를 선택합니다) 큰 수가 앞에 있을수록 좋고 k+1개 뒤의 수가 가장 앞에 오려면 k+1개 이상의 수를 지워야 하기 때문이죠.
계속해서 두 번째 자리의 수는 앞에서 선택된 수 뒤부터 k+2번째까지 수 중 최댓값이 됩니다.
k+2개 뒤의 수가 두 번째 수가 되려면 k+2 - (앞에서 선택한 수의 개수) = k+1개 이상의 수를 지워야 하기 때문입니다.
비슷한 방법으로 n-k 자리를 결정하면 문제를 해결할 수 있습니다.
소스와 같이 큐를 구현하면 안에 있는 수열들을 단조 감소하게 유지해서 매 자리를 결정할 때마다 최댓값을 구할 수 있습니다.
처음 STR[0...k-1]을str[0...k-1]를 push 해놓으면
다음 push 이후 front 값은 앞의 k+1개 수 중 최댓값(1)
다음 pop, push 이후 front 값은 (1) 이후 ~ k+2번째 수 중 최댓값(2)
다음 pop, push 이후 front 값은 (2) 이후 ~ k+3번째 수 중 최댓값(3)
...
이런 식으로 구할 수 있습니다.