[ boj : 2812 ] 크게 만들기

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

2812번: 크게 만들기

문제 : n자리의 수가 주어지고 k개를 지워서 가장 큰 수를 만들어라

해설 : 이런 문제를 자주 접해보지 않았더라면,,,,해맸을 수도 있는 문제입니다.

문제의 특성을 파악하고 확실히 기억하도록 노력합시다. 먼저 가장 큰수가 될 조건은 가장 큰 숫자부터 차례대로 만들어지면 되겠죠.

그러면 먼저 숫자들을 쌓아놓고 현재 위치해 있는 숫자가 쌓아놓은 숫자보다 크다면?? 쌓아놓은 숫자는 필요가 없어집니다. 그러면 버리면 되겠죠. 언제까지 버려야 될까요??? 바로 맨위의 숫자가 현재 고른 숫자보다 클때까지 버리면 됩니다.

이 설명을 들으면 바로 알아채야 합니다. 바로 '스택' 자료구조를 사용하는 거구나! 라고요.

스택을 사용해서 숫자들을 하나씩 집어넣고 top 의 숫자보다 큰 숫자가 오면 pop 을 실행합니다. top의 숫자가 현재 위치한 숫자보다 클때까지요.

그러면 스택에 저장되어있는 숫자들을 절대로 작은 숫자가 큰숫자보다 앞서 나오는 경우는 존재하지 않습니다. 이걸 k가 0이 될때까지 반복하며 됩니다.

그럼 만약 연산을 다 끝냈는데 k가 0보다 큰 경우는 어떻게 해야되나요???

이 부분은 굳이 생각할 필요없이 에초에 출력을 (n-k) 만큼만 출력하면 됩니다. 만약 k가 0이상이라는 뜻은 작은수가 큰수보다 앞서 있는 경우는 없다는 의미이며 그렇다면 맨뒤에서 차례대로 k가 0이 될때까지 지워주면 문제의 정답을 도출할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n, k;
	string str;
	stack<char> st;
	cin >> n >> k >> str;

	int cnt = k;
	for (int i = 0; i < str.length(); i++) {
		while (!st.empty() && st.top() - '0' < str[i] - '0' && k > 0) {
			st.pop();
			k--;
		}
		st.push(str[i]);
	}
	string ans;
	while (!st.empty()) {
		ans += st.top();
		st.pop();
	}
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < n - cnt; i++)
		cout << ans[i];
	return 0;
}