[BOJ/C++] 2812 크게 만들기

그리디 알고리즘과 스택을 이용하여 문제를 해결할 수 있습니다.

문자열을 순회하며 다음과 같이 진행합니다.
1. 스택이 비어있거나 K개만큼 제거했을 때
- 스택에 push
2. 그렇지 않고 스택의 top이 $i$번째 숫자보다 클 때
- 스택에 push
3. 스택의 top보다 $i$번째 숫자가 크다면
- 스택이 비어있지 않고 K만큼 제거하지 않고 stack의 top이 $i$번째 숫자보다 작을때 까지 스택에 pop
- 이후 크거나 같은 숫자라면 스택에 push
4. 모든 숫자에 대해 진행했음에도 아직 K개만큼 빼지 않았다면 스택의 상단에는 작은 숫자 순서로 남아있으므로 K개만큼 스택에서 빼면됩니다.

스택의 숫자를 뽑아서 문자열에 더하고 이후 reverse 하는 것을 없애기 위해 편의상 deque를 사용했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <string>


using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, K;
    cin >> N >> K;

    deque<int> dq;
    string answer = "";

    string input;
    cin >> input;

    for(int i=0; i<N; i++)
    {
        int temp = input[i]-'0';

        if (dq.empty() || K<=0)
            dq.push_back(temp);
        else
        {
            if (dq.back() > temp)
                dq.push_back(temp);
            else
            {
	            while(!dq.empty() && dq.back()<temp && K>0)
	            {
                    dq.pop_back();
                    K--;
	            }
                dq.push_back(temp);
            }
        }
    }

    for(int i=0; i<dq.size()-K; i++)
    {
        cout << dq[i];
    }

    return 0;
}