백준 2812번 크게 만들기[C++]

1. 문제풀이

이번에 풀어본 문제는 백준 2812번 크게 만들기입니다. 문제의 유형은 그리디입니다. 스택을 사용해서 적절하게 숫자를 버리는 방법을 선택하면 풀 수 있습니다. 현재 삽입할 숫자가 스택의 top보다 크다면, 스택에 있는 숫자들을 빼내주면서 지우면, 스택에 담겨 있는 숫자들로 가장 큰 수를 만들 수 있습니다. 여기서 주의할 점은 위와 같은 로직을 수행하고 나서도 삭제해야 할 숫자가 남아있다면 스택의 top부터 제거해 주면 됩니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, k;
string num;

int main() {
  fastio(nullptr, false);
  cin >> n >> k >> num;
  
  stack<char> stk;
  for(int i = 0; i < n; i++){
    while(k && stk.size() && stk.top() < num[i]){
      k--;
      stk.pop();
    }
    stk.push(num[i]);
  }
  while(k--) stk.pop();
  
  string ans{};
  while(stk.size()){
    ans += stk.top();
    stk.pop();
  }
  reverse(all(ans));
  cout << ans;
}

 

3. 제출결과