[C++] 백준 2812번: 크게 만들기

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

2812번: 크게 만들기

중요풀이

이 문제는 그리디 알고리즘을 활요한 문제입니다. 앞에서부터 순차적으로 보았을 때 다음 자리 숫자보다 현재 자리 숫자가 작다면 현재 자리 숫자를 제거해주는 식으로 루프를 진행해주고 이 과정이 끝나고도 K자리를 다 빼지 않았다면 남은 K의 숫자만큼의 자리를 뒤에서부터 빼주는 과정을 반복합니다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, K, i = 0;
	string num;
	vector<char>v;
	cin >> N >> K;
	cin >> num;

	while (i != num.size()) {
		while (K != 0 && !v.empty() && v.back() < num[i]) {
			v.pop_back();
			K--;
		}
		v.push_back(num[i]);
		i++;
	}
	
	//아직 못 빼준것이 있다면
	while (K--)
		v.pop_back();
	
	for (int i = 0; i < v.size(); i++)
		cout << v[i];

	return 0;
}