[2812]크게 만들기

www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

받은 입력 문자열을 하나씩 스택에 넣고

스택의 top위치 값이 현재 값보다 크면 최대 K번 pop한다

그럼 내림차순 형태의 수가 나오게 된다.

모두 같은 숫자일 경우에는 더이상 지워지지 않으므로

마지막에 N-K길이의 문자열로 출력하도록 했습니다

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstdio>

using namespace std;

int main() {
    int N, K;
    cin>>N>>K;
    string s;
    cin>>s;
    stack<int> st;
    int d = 0;

    st.push(s[0]-'0');

    int limit = 0;
    for(int i = 1; i<N; i++){
        while(limit<K){
            if(!st.empty()&&st.top()<s[i]-'0'){
                d = st.top();
                st.pop();
                limit++;
            }
            else{
                break;
            }
        }
        d = s[i]-'0';
        st.push(s[i]-'0');
        d = st.size();
    }

    string ans = "";

    while(!st.empty()){
        ans += st.top() + '0';
        st.pop();
    }
    reverse(ans.begin(), ans.end());
    for(int i = 0; i<N-K; i++){
        cout<<ans[i];
    }
}