백준 2812번: 크게 만들기

 

풀이

  답답해서 결국 풀이를 찾아봤다.

  그냥 가장 작은 숫자부터 지워주면 되는 줄 알았는데, 덱 또는 스택과 그리디 알고리즘을 함께 사용해야 하는 문제였다. 첫번째 숫자부터 차례대로 덱에 넣어주면서 지금 숫자가 덱에 있는 숫자보다 더 큰 지 검사한다. 만약 덱에 있는 숫자보다 더 크다면 덱에 저장된 작은 숫자들을 모두 pop해 지워주고, 지운 개수만큼 K를 하나씩 감소한다. 만약 지운 개수가 적어 K가 남아있다면 (N-K) 개 만큼 덱의 앞에서부터 출력해주면 된다.

 

 

코드

#include <iostream>
#include <deque>

using namespace std;

int N, K;
string input;
deque<char> d;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	cin >> N >> K;
	cin >> input;

	for (int i = 0; i < N; i++) {
		while (!d.empty() && K && d.back() < input[i]) {
			d.pop_back();
			K--;
		}
		d.push_back(input[i]);
	}

	for (int i = 0; i < d.size() - K; i++)
		cout << d[i];

	return 0;
}