[백준] 크게 만들기

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

2812번: 크게 만들기

stack을 이용하는 문제입니다.

 

문제부터 간단하게 요약하면, 

N자리 숫자가 주어지는데, 이 숫자중에서 K개를 지워서 만들 수 있는 가장 큰 수를 출력해야 하는 문제입니다.

 

<Solution>

간단하게 예시를 통해 알고리즘을 생각해보면, 

1924를 보면 stack에 하나씩 넣는데, 1보다 큰 9가 들어오면, 1을 pop시키는 형태로 구현을 하면 된다는 생각이 듭니다.

 

조금 더 디테일 하게는 더 큰 숫자를 집어넣기 전에 stack을 pop하는데, pop은 그 숫자보다 작은 애들을 모두 pop해주어야 하고, 이 때 총 지운 숫자가 K보다 많아지는 경우는 pop을 하지 않습니다. 

 

이러한 로직을 이용하여 구현하면 되고, 실제 코드는 아래와 같습니다. 

#include <iostream>
#include <stack>
#include <cstring>
 
using namespace std;
#define MAXN ((int)5e5)
int N, K;
char str[MAXN + 10];
void InputData() {
    cin >> N >> K;
    cin >> str;
}
 
void solution(){
    int erase = 0;
    stack<int> stk; 
    int cur_index = 0;
     
    while(cur_index <N){

        while(erase < K && !stk.empty() && stk.top() < str[cur_index] - '0'){
            stk.pop();
            erase+=1;
        }
        stk.push(str[cur_index]-'0');
        cur_index+=1;
    }
 
    while(erase < K){
        stk.pop();
        erase+=1;
    }
  
    char ans[MAXN + 10];
    int i = stk.size()-1;
    while(!stk.empty()){
        ans[i--] = stk.top() + '0';
        stk.pop();
    }
    cout << ans << endl;
}
 
 
int main() {
    InputData();

    solution();

    return 0;
}