BOJ 2812번: 크게 만들기
BOJ
문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
풀이
스택을 이용한다. 스택에 배열의 순서대로 하나씩 넣으면서 현재 지운 숫자가 k보다 작고 스택이 비어있지 않을 때 스택의 맨 위 숫자가 넣을 숫자보다 작으면 스택의 맨 위 숫자를 제거하고 현재 지운 숫자의 카운트를 올려준다. dq를 출력할 때 n - k 만큼의 숫자를 출력해야 하고 지우지 못한 숫자가 존재할수도 있기 때문에 (숫자가 계속 작아지는 경우) 스택의 크기에서 (k - 카운트) 만큼을 빼주면 나머지를 지우고 출력할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
string s; cin >> s;
deque<int> dq;
int cnt = 0;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.back() < s[i] - '0' && cnt < k) {
dq.pop_back();
cnt++;
}
dq.push_back(s[i] - '0');
}
for (int i = 0; i < dq.size() - (k - cnt); i++) {
cout << dq[i];
}
return 0;
}