[BOJ] 2812. 크게 만들기 ✔

2812. 크게 만들기

1. 문제

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

2. 입력

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

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

3. 출력

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

4. 풀이

C++

#include <iostream>
#include <queue>
#include <string>
#define ioboost ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;

int N, K;
string digit;

void Input()
{
    cin >> N >> K;
    cin >> digit;
}

void Solve()
{
    deque<char> dq;
    
    for (int i = 0; i < N; ++i)
    {
    	// 현재 자리의 숫자보다 deque에 있는 숫자가 작을 때마다 pop (K > 0일 때)
        while (K && !dq.empty() && digit[i] > dq.back())
        {
            dq.pop_back();
            --K;
        }
       dq.push_back(digit[i]);
    }
    
    // K가 0보다 크게 남을 시, deque 안의 숫자들이 내림차순으로 들어있음
    // 때문에 deque 끝에서부터 남은 K만큼 숫자 무시
    for (int i = 0; i < dq.size() - K; ++i)
        cout << dq[i];
}


int main()
{
    ioboost;
    Input();
    Solve();
}