백준 2812번 크게 만들기

🔒[문제 url]

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

🔑알고리즘

자료구조를 활용하는 그리디 문제였다.
1. 숫자의 앞자리수부터 살펴본다.
2. 현재의 수가 이전의 수보다 크다면, 이전의 숫자를 모두 지워준 후 현재의 수를 push한다.
이때, 지우는 과정은 자료구조가 비거나 현재의 수가 이전의 수보다 크지 않을때까지 반복한다. 또한, k번을 초과하여 지우지않도록 주의한다.
3. 현재의 수가 이전의 수보다 작거나 같다면, 현재의 수를 push한다.

deque와 stack 모두 활용 가능하며, 알고리즘은 동일하다.
다만, 출력 방식은 약간 차이가 있으므로 주의하자.

• 출력 시 주의할 점은?
  • 입력이 6 3 222122인 경우, 답은 222이나
    자료구조에 이전의 수와 같은 값은 push하므로 22222가 들어있다.
    따라서 n - k만큼만 출력하도록 한다.
    
• stack 출력 방식 : 앞자리수가 가장 밑에 있으므로 순서를 역으로 옮긴 후 n - k만큼 출력한다.
• deque 출력 방식: 앞에서 n - k만큼 출력한다.
  
  두가지 version의 코드 모두 살펴보도록 하자.

🐾부분 코드

// DEQUE ver.

int eraseCnt = k;
for (int i = 0; i < n; i++)
{
	
	while (!dq.empty() &&
    	   eraseCnt &&
    	   dq.back() < num[i] - '0')
    // dq가 비어있지않고, 지울 기회가 남았으며, 현재 수가 이전의 수보다 크다면
	{
		dq.pop_back(); // 앞의 수를 지운다.
		eraseCnt--;
	}
	dq.push_back(num[i] - '0');
}// for end

// STACK ver.

int eraseCnt = 0; // k가 되면 더이상 지우지않음
for (int i = 0; i < n; i++)
{
	int now = num[i] - '0';

	{
		// stack empty라면 push
		if (st.empty()) st.push(now);
		// 현재 수가 stack top보다 크면
		else if (now > st.top())
		{
			// stack top이 now보다 작으면 계속 pop
			while (!st.empty() && now > st.top())
			{
				if (eraseCnt == k) break;
				st.pop();
				eraseCnt++;
			}
			// pop이 끝나면 push
			st.push(now);
		}
		// 현재 수가 stack top 이하이거나, 더이상 지울수없다면 push
		else if (now <= st.top() || eraseCnt == k) st.push(now);

	}
}// for end

<조건에 따라 자료구조에 값을 push>
알고리즘에서 언급한 조건에 따라, 지울 값이 있다면 반복적으로 지운 후 값을 push한다. 이때 num은 string type이므로, ascii code를 이용해 int type으로 push한다.

// DEQUE ver.

// 같은 숫자는 무조건 push되기때문에 필요한 길이만큼만 출력 : i < n - k
for (int i = 0; i < n - k; i++)
{
	cout << dq.front();
	dq.pop_front();
}

// STACK ver.

//move for output
while (!st.empty())
{
	ans.push(st.top());
	st.pop();
}
	
// output
for (int i = 0; i < n - k; i++)
{
	cout << ans.top();
	ans.pop();
}

<출력 부분>
n - k만큼 출력한다. stack 출력시 순서를 역으로 바꾼 후 출력한다.

🪄전체 코드

// DEQUE ver.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <numeric>
#include <stack>
using namespace std;

int n, k;
string num;
deque<int> dq;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> num;
}



void SOLVE()
{
	int eraseCnt = k;
	for (int i = 0; i < n; i++)
	{
		// 지울 횟수가 남았고 deque가 비어있지 않으며 현재 수보다 앞의 수가 더 작은동안 
		while (eraseCnt && !dq.empty() && dq.back() < num[i] - '0')
		{
			dq.pop_back();
			eraseCnt--;
		}
		dq.push_back(num[i] - '0');
	}// for end

	// 같은 숫자는 무조건 push되기때문에 필요한 길이만큼만 출력 : i < n - k
	for (int i = 0; i < n - k; i++)
	{
		cout << dq.front();
		dq.pop_front();
	}

}

int main()
{
	INPUT();

	SOLVE();
}

// STACK ver.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <numeric>
#include <stack>
using namespace std;

int n, k;
string num;
stack<int> st, ans;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> num;
}



void SOLVE()
{
	int eraseCnt = 0; // k가 되면 더이상 지우지않음
	for (int i = 0; i < n; i++)
	{
		int now = num[i] - '0';

		{
			// stack empty라면 push
			if (st.empty()) st.push(now);
			// 현재 수가 stack top보다 크면
			else if (now > st.top())
			{
				// stack top이 now보다 작으면 계속 pop
				while (!st.empty() && now > st.top())
				{
					if (eraseCnt == k) break;
					st.pop();
					eraseCnt++;
				}
				// pop이 끝나면 push
				st.push(now);
			}
			// 현재 수가 stack top 이하이거나, 더이상 지울수없다면 push
			else if(now <= st.top() || eraseCnt == k) st.push(now);

		}
	}// for end

	//move for output
	while (!st.empty())
	{
		ans.push(st.top());
		st.pop();
	}
	
	// output
	for (int i = 0; i < n - k; i++)
	{
		cout << ans.top();
		ans.pop();
	}

}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

자료구조를 활용한 문제는 확실히 해당 자료구조의 숙련도에 따라 코드의 간결함이 천차만별이 되는듯하다. 처음에는 stack으로 접근했는데, 다 풀고나서야 deque로 접근하면 더 간결해질 수 있다는걸 깨달았다. 특히나 출력부분에서! 대부분의 문제가 자료구조는 큰 도구가 되는만큼, 다양한 자료구조를 능숙하게 익히는 것이 중요할 것같다.