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

2812번: 크게 만들기

 

문제

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

2812번: 크게 만들기

 

 

풀이

N자리 숫자에서 숫자 K개를 지워 얻을 수 있는 가장 큰 수를 구하는 문제다. 결과는 N-K자리 숫자가 되는데 앞자리 수가 클수록 큰 수가 될 것은 자명하다. 차례로 순회하며 이번 수보다 앞에 있으면서 작은 수를 지우면 될 것이다. 만약 수를 더 지워야 하면 가장 끝자리 수를 지우면 된다. 스택을 사용해 해결할 수 있고 스택과 같은 형태이면서 값 접근이 용이한 벡터를 사용해 풀었다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  string s;
  cin >> n >> k >> s;
  vector<int> v;
  for (char i : s) {
    while (!v.empty() && v.back() < i - '0' && k) {
      v.pop_back();
      k--;
    }
    v.push_back(i - '0');
  }
  while (k--)
    v.pop_back();
  for (int i : v)
    cout << i;
  cout << '\n';
  return 0;
}