[BOJ] 2812번 : 크게 만들기

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

2812번: 크게 만들기

---

풀이

가장 큰 수를 만들기 위해선 수를 문자열로 보았을 때, 앞쪽 수가 무조건 큰 것이 유리하다.

따라서, 오름차순 모노톤 스택을 관리해 주면 된다. 즉, 스택의 안쪽에 있을수록 큰 숫자가 존재하도록 한다.

구체적으로는, (스택의 top < 들어갈 원소) && (k > 0) 일때,  스택에서 pop하면서 k를 1씩 감소하면서 관리하면 된다.

 

숫자를 정확히 k개 지우는 것을 처리하기 위해 다음과 같이 처리해주었다.

• (k > 0)일때만 스택에서 pop을 하도록 하여, 숫자를 k개 초과하여 지우지 않도록 하였다.
• 스택의 사이즈가 n - k를 초과하면 스택의  top에서부터 하나씩 빼도록 하여, 숫자를 k개 미만으로 지우지 않도록 하였다.

 

이때, 덱을 이용하면 출력이 편해진다.

---

코드

ll n, k;
string s;
deque<char> dq;

void solve()
{
    cin >> n >> k >> s;
    ll kk = k;
    for (int i = 0; i < n; i++)
    {
        while (!dq.empty() && dq.back() < s[i] && k > 0)
        {
            dq.pop_back();
            k--;
        }
        dq.push_back(s[i]);
    }
    while (dq.size() > n - kk) dq.pop_back();
    while (!dq.empty())
    {
        cout << dq.front();
        dq.pop_front();
    }
}