백준 2812번: 크게 만들기

[문제 링크]

2812번: 크게 만들기

---

입력받은 숫자의 순서를 바꿀 수 없기 때문에 앞에서부터 탐색하여 K가 0이 되기 전까지 가능한 큰 숫자가 앞에 위치하도록 숫자를 지우는 것이 이 문제의 핵심이었다.

 

입력받은 숫자를 앞에서부터 컨테이너에 담으면서 만약 K가 1이상이고, 앞에 먼저 담은 숫자가 현재 담을 숫자보다 작을 경우 K를 1 감소시키면서 컨테이너에 담긴 숫자를 제거하는 방법으로 구현하였다.

 

담을 때는 LIFO 방식이 필요하지만, 출력할 때는 FIFO 방식이 필요하므로 deque 컨테이너를 사용하였다.

---

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

void Greedy(string& number, int N, int K)
{
	deque<char> dq;
	
	for (int i = 0; i < N; i++)
	{
		while (!dq.empty() && K != 0 && dq.back() < number[i])
		{
			dq.pop_back();
			K--;
		}

		dq.push_back(number[i]);
	}

	while (K--)
		dq.pop_back();

	while (!dq.empty())
	{
		cout << dq.front();
		dq.pop_front();
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);

	int N, K;
	cin >> N >> K;

	string number;
	cin >> number;

	Greedy(number, N, K);

	return 0;
}

알고리즘 200일 프로젝트 - 129 day