백준-2812번: 크게 만들기

Boj handle: wlsgur348

2812번: 크게 만들기

N자리 숫자에서 K개의 숫자를 지워서 큰 수를 만들어야한다.

어떤 방법이 있을까 고민을 엄청 하다가 결국 검색을 해봤었다.

일단 이전 보다 큰 수가 되려면 앞의 숫자가 뒤의 숫자보다 작으면 안된다.

예시의 숫자 1924를 보면 맨 앞자리 1이 있는 한 뒤의 어떤 숫자를 제거해도 200을 넘을 수 없다.

따라서 앞부터 순서대로 이전 숫자보다 큰 숫자가 나오면 deque의 숫자가 다음 숫자보다 클 때까지 제거해준다.

다음을 순서대로 알고리즘을 나타내면

1삽입->1제거,9삽입->2삽입->2제거,4삽입

1삽입->1제거,2삽입->2제거,3삽입->1삽입->1제거,2삽입->3삽입(k횟수 이미 다 채움)->4삽입

순으로 진행된다.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
deque<char>q;
int main() {
	int N, K;
	string input;
	cin >> N >> K;
	cin >> input;
	for (int i = 0; i < (int)input.size(); i++) {
		while (K && !q.empty() && q.back() < input[i]) {
			q.pop_back();
			K--;
		}
		q.push_back(input[i]);
	}
	for (int i = 0; i <(int)q.size() - K; i++) {
		cout << q[i];
	}
	return 0;
}