이번 문제는 스택 자료구조와 그리디 알고리즘을 활용하여 해결하는 문제였다.

• 숫자를 string형으로 받는다.
• string형 숫자를 orig라는 vector에 char형으로 넣는다.
• orig의 앞에서 부터 result에 넣어준다. 이때 뒤에 등장하는 수보다 작은 수들은 모두 빼준다.
• 제거되지 않은 수가 있을 수 있으므로 while(k--)를 통해 제거해준다.

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, k;
string num;
vector<char> orig;
vector<char> result;

void Input(){
    cin>>n>>k;
    cin>>num;
    for(int i=0; i<n; i++){
        orig.push_back(num[i]);
    }
}

void Solution(){
    int idx=0;
    while(idx!=num.size()){
        while(k!=0&&!result.empty()&&result.back()<orig[idx]){
            result.pop_back();
            k--;
        }
        result.push_back(orig[idx]);
        idx++;
    }
    while(k--){
        result.pop_back();
    }
    for(int i=0; i<result.size(); i++){
        cout<<result[i];
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}