2812(크게 만들기)

난이도: 골드 3

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

2812번: 크게 만들기

 

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

풀이

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int N, K;

int main()
{
    cin >> N >> K;

    string s;
    cin >> s;

    deque<char> dq;

    for (int i = 0; i < s.length(); i++)
    {
        while (K > 0 && !dq.empty() && dq.back() < s[i])
        {
            dq.pop_back();
            K--;
        }
        dq.push_back(s[i]);
    }

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