문제 풀이

• 숫자가 최대 50만 자리이기때문에 string 형태로 입력을 받아야한다.

스택을 사용하여 먼저 맨처음에는 입력받은 문자열 s의 front -> s[0]을 스택에 넣어주고 시작한다.

이후 s[i]가 스택의 top보다 작거나 같으면 그냥 스택에 넣어주고
s[i]가 스택의 top보다 크다면 s[i]보다 작은것들은 스택에서 pop해주는데 남은 지울 수 있는 숫자 만큼만 지워준다.

for문을 다 돌았는데 아직 지워야 하는 숫자가 남았다면 그만큼 스택에서 pop 해준다.

이제 마지막으로 출력만 하면되는데 스택은 출력해야되는 숫자의 반대로 되어있으므로 벡터를 따로 선언해서 그곳에 넣어주고 마지막 원소부터 출력해주면 된다.

여기서 벡터가 비어있다면 숫자가 모두 지워진것이므로 0을 출력하면된다.

문제 링크

boj/2812

소스코드

PS/2812.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;


int main(void)
{
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	stack<char> stk;
	stk.push(s[0]);
	for (int i = 1; i < s.size(); i++)
	{

		if (s[i] <= stk.top())
		{
			stk.push(s[i]);
		}
		else if (s[i] > stk.top())
		{
			while (k && !stk.empty() && stk.top() < s[i])
			{
				stk.pop();
				k--;
			}	
			stk.push(s[i]);
		}
	}
	while (k && !stk.empty())
	{
		stk.pop();
		k--;
	}
	vector<char> v;
	
	while (!stk.empty())
	{
		v.push_back(stk.top());
		stk.pop();
	}
	if (v.empty())
	{
		cout << 0;
	}
	else {
		for (int i = v.size() - 1; i >= 0; i--)
			cout << v[i];
	}
}