[백준/BOJ] 백준 2812번 : 크게 만들기

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

2812번: 크게 만들기

 

앞자리 숫자를 크게 할수록 더 큰 숫자를 만들 수 있기 때문에, 숫자를 앞에서부터 확인하여 이전의 숫자보다 지금 숫자가 더 크다면 이전의 숫자를 지우는 방법을 통해 문제를 해결했다.

deque를 이용해 들어오는 숫자들을 저장하면서, 이전에 deque에 들어왔던 숫자들을 뒤에서부터 확인하여(최근에 deque에 들어온 순서로 확인) 지금 들어오는 숫자보다 작다면 지울 수 있는 만큼 deque에서 제거하는 방법으로 구현했다.

 

코드

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

int n, k;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	string input;
	cin >> input;

	deque<char> result;
	int erase_cnt = 0;
	for (int i = 0; i < input.size(); i++) {

		if (result.empty()) { //deque가 비어 있을때
			result.push_back(input[i]);
			continue;
		}

		if (erase_cnt == k) { //k개를 다 지웠을때
			result.push_back(input[i]);
			continue;
		}

		// i 번째 수 앞을 지우는것이 이득인 경우 일때 지운다
		while ((erase_cnt < k) && (!result.empty()) && (result.back() < input[i])) {
			result.pop_back();
			erase_cnt++;
		}

		result.push_back(input[i]);
	}

	while (erase_cnt < k) { //아직 k개를 다 지우지 못했을때. 뒤에서 부터 지운다
		result.pop_back();
		erase_cnt++;
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}

	return 0;
}