백준 2812, 크게 만들기

개요

문제 링크
골드 3, Greedy
N자리 수에서 K개를 제외해 얻는 최댓값

---

접근

1. 그리디한 인간이 되자. 우선 귀찮은 인간은 k개를 제외할지, n-k개를 선택할지 부터 선택할 것이다. 여기까지 한 5-10분 고민한 것 같고, 나는 n-k개를 선택하는 방법에 대해 생각하기로 했다.
2. 어떻게 선택한다는거냐, 아래 예시를 보자.

// n=10, k=4, 6개를 골라야 함.
// 가장 큰 자리를 구하는 경우
4177252841
|---|

41772 중에 가장 큰 수를 고르면 된다. 왜냐?

1) 우선 첫번째 자리를 선택할 때 최소한 뒤에 5개의 수는 남겨놔야 한다. 두번째 자리는 4개, 세번째 자리는 3개... 이렇게 이어진다.
2) 최선의 선택은 가장 높은 자리수를 가장 큰 값으로 하는 것이다. 즉 그리디하게 선택하자면 0~n-k 에 대해 [i, n-k+i] 중 고르지 않은 최댓값을 골라야 한다.

3. 그런데 이렇게 선택하면 문제가 생긴다.

// n=10, k=4
4673252841
46X3252841 // i=0 {7}
4XX3252841 // i=1 {7,6} (x)

이미 지나온 값을 골라버린다. 그래서 나는 매번 고르는 지점을 갱신하고, [이전에고른지점+1, n-k+i] 의 최댓값을 뽑는 방식으로 갔다.

// n=10, k=4
4673252841
46X3252841 // i=0 max(0~5) {7}
46X32X2841 // i=1 max(3~6) {7,5}
46X32XXXXX // {7,5,2,8,4,1}

여기까지 머리 싸매고 해봤는데 TLE가 떴다. 세그트리 쓰면 될지도..?
세그트리 써봤다. 안된다. O(nlogn)도 허용되지 않는 것 같다. 풀이는 아래에...
사실 여기까지는 정석풀이보다 이해가 더 쉬울 것 같아 작성해봤다.

4. 사실 가장 먼저 고민했던 방법, k개를 제외하냐, n-k개를 선택하냐에서 k개를 제외하는 방법을 선택해야 했다. 제외하는 방식은? stack에서 뽑아버리면 되고, 제외하는 경우는? 들어오는 값보다 stack의 마지막 값이 작을 때, k가 0보다 클 때이다.
   뭔 소린가 하니,

// n=10, k=4
4673252841 // i=0, k=4) {4}
O673252841 // i=1, k=4) 4<6 -> 4탈락 {6}
XO73252841 // i=2, k=3) 6<7 -> 6탈락 {7}
XXO3252841 // i=3, k=2) 7>=3 -> 7생존 {7,3}
XXOO252841 // i=4, k=2) 3>=2 -> 3생존 {7,3,2}
XXOOO52841
// i=5, k=2) 2<5 -> 2탈락 {7,3,5}
// i=5, k=1) 3<5 -> 3탈락 {7,5}
XXOXXOOOOO // => k=0 이므로 전부 생존, {7,5,2,8,4,1}

이러면 자동으로 앞서 말한 [prev+1,n-k+i]의 최댓값이 골라지는데 이유는

1) 이전에 고른 위치에 대한 업데이트는 자동으로 된다. 왜냐? 이미 그 앞에 원소는 stack에서 모두 빠져있기 때문
2) 그럼에도 n-k개가 보존되는 이유는? 예를들어 위 예시에서 4673292841이었다면? {7,9}에서 7빠지고 {9}되는거 아닌가? 아님. 이유는 k개 까지만 빼니까 이미 3,2를 빼서 더 뺄 수 없다.

5. 마지막으로 아직 뺄 것이 남았을 수 있다. 아래 예시를 보자.

// n=6, k=3
987655
O87655 // 9>=8, 9생존 {9,8}
OO7655 // 8>=7, 8생존 {9,8,7}
OOO655 // 7>=6, 7생존 {9,8,7,6}
OOOO55 // 6>=5, 6생존 {9,8,7,6,5}
OOOOO5 // 5>=5, 5생존 {9,8,7,6,5,5} k=3

이렇게 되면 뒤에서부터 뽑아주면 된다. 왜냐? 앞서 그리디하게 선택하는 것은 가장 높은 자리수를 가장 큰 값으로 하는 것이라 했는데, 자리가 높을수록 크지 않은 경우는 더 이상 뺄 수 없는 경우밖에 없다.
이게 무슨 말과 같냐, 만약 k가 남아있다면 무조건 descending order라는 것이다. 그래서 뒤에서부터 빼주면 된다.

---

Pseudo code

for (c : string)
    while (k && last < c)
        stack.pop(), k--
    stack.push(c)

// 아직 제외할 것이 남았다면
while (k--)
    stack.pop()

cout << reverse(stack)

---

Source code

#include <iostream>
#include <stack>
using namespace std;

int n, k;
string s, b;
stack <char> a;

int check(char c) {
    if (!k)
        return 0;
    if (a.empty())
        return 0;
    if (a.top() >= c)
        return 0;
    return 1;
}

int main() {
    cin >> n >> k >> s;

    for (int i=0; i<n; i++) {
        while (check(s[i]))
            a.pop(), k--;
        a.push(s[i]);
    }
    while (k--)
        a.pop();

    int l = a.size();
    b.resize(l);
    while (!a.empty()) {
        b[--l] = a.top();
        a.pop();
    }
    cout << b;
}

// segtree, TLE
// O(N+KlogN)

#include <stdio.h>

#define N 500000
#define o 1,n,1
#define node int s,int e,int n
#define left s,m,n*2
#define right m+1,e,n*2+1

int tree[N*4], p, q;
char str[N], a[N];

int f(int i, int j) {
    return str[i]>=str[j]?i:j;
}

int init(node) {
    if (s==e)
        return tree[n]=s;
    int m = (s+e)/2;
    return tree[n]=f(init(left),init(right));
}

int find(node) {
    if (q<s || e<p)
        return 0;
    if (s==e)
        return tree[n];
    int m = (s+e)/2;
    return f(find(left),find(right));
}

int main() {
    int n, k;
    scanf("%d%d%s",&n,&k,str+1);

    init(o);
    k = n-k;
    p = 1, q = n-k+1;
    for (int i=0; i<k; i++) {
        if (p < q)
            p = find(o);
        a[i] = str[p];
        p++, q++;
    }
    printf("%s", a);
}