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

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

2812번: 크게 만들기

 

스택 자료구조 문제다.

 

N자리 숫자에서 K개를 지워서 만들 수 있는 가장 큰 수를 찾는 문제다.

앞에서부터 순회해 스택에 숫자를 push한다.

push 할 숫자가 stack에 들어있는 숫자보다 크다면 pop을 한다.

스택의 top보다 값이 작을 때까지 or k 범위 내에서 pop을 반복한다.

 

위 작업이 끝나면 스택에 남은 값들을 pop하면서 남은 문자열과 합쳐 답을 구한다.

 

#include <iostream>
#include <stack>
using namespace std;

int n, m;
int arr[500000];

int main() {
	cin >> n >> m;
	string str;	cin >> str;

	stack<char> s;
	int cnt = 0;
	int i;
	s.push(str[0]);
	for (i = 1; i < str.size(); i++) {
		if (cnt == m) break;
		while (!s.empty() && s.top() < str[i] && cnt < m) {
			s.pop();
			cnt++;
		}
		s.push(str[i]);
	}

	string res = "";
	while (!s.empty()) {
		res = s.top() + res;
		s.pop();
	}

	cout << (res + str.substr(i,s.size() - i)).substr(0, str.size() - m);
}