[c++] 백준 2812 크게 만들기

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

2812번: 크게 만들기

숫자는 자리수가 큰 쪽이 숫자의 대소를 결정하기 때문에

자리수가 큰 쪽에 큰 수가 오게 숫자를 최대한 내림차순으로 만들어 준다.

#include<bits/stdc++.h>
using namespace std;
stack<char> stk; //스택을 이용해 답을 구한다.
vector<char> ans; //역으로 출력하기 위해 답 저장
int main(){
    int n,k; cin>>n>>k;
    string num; cin>>num;
    for(int i=0; i<n; i++){
        // 스택이 비어있거나
        //숫자를 다 지웠을때
        if(k == 0 || stk.empty()) 
            stk.push(num[i]);
        else{
            // 이전 숫자가 현재 숫자보다 작을때
            // 내림차순으로 만들기 위해 제거
            if(stk.top() < num[i]){
                char tmp = num[i];
                // 내림차순이 될 때까지 제거
                while(!stk.empty() && stk.top() < tmp && k != 0){
                    k--;
                    stk.pop();
                }
                stk.push(num[i]);
            }
            else if(stk.top() >= num[i]) // 이미 내림차순일때 스택에 넣기
                stk.push(num[i]);
        } 
    }
    // 출력
    while(!stk.empty()){
        ans.push_back(stk.top());
        stk.pop();
    }
    for(int i=ans.size()-1; i>=k; i--) cout << ans[i];
    return 0;
}