백준 2812 - 크게 만들기

문제링크

• 백준 2812

문제설명

• 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
• 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
• N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

문제접근1 (시간초과)

• 시간초과로 문제를 해결하지 못했지만, 처음에 풀이했던 방법은 다음과 같다.
• N자리 숫자 -> (N-K)자리 숫자로 변환하기 위해 (N-K)자리 숫자의 각 자리에 최선의 값을 선택한다.
  • (N-K)자리 숫자의 앞자리부터 결정하기 위해서 처음에 주어진 숫자 문자열에서 선택 가능한 숫자들을 추린다. 후보군을 만들 때는 해당 숫자를 선택했을 때 뒤에 나머지 숫자들을 채우기 위한 충분한 개수의 숫자가 있는지를 기준으로 한다.
  • 선택된 숫자의 앞쪽에 위치한 숫자들은 뒤쪽에 위치할 수 없기 때문에 나머지 자리를 결정하기 위한 숫자 후보군은 현재 선택된 숫자의 뒤에 위치한 숫자들로만 선정될 수 있다.
  • 이와 같은 과정을 모든 자리에 대해 반복한다.

  

구현

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

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

	int N, K;
	string strNum;

	cin >> N >> K;
	cin >> strNum;
	
	int curLength = N - K;
	int curPos = 0; // 마지막으로 선택한 숫자의 인덱스. 해당 인덱스 뒤에서만 선택할 수 있음
	string ans;
	for (int i = curLength; i > 0; i--)
	{
		int pos = curPos;
		int backLength = strNum.length() - pos - 1;
		char maxNum = strNum[pos];
		while (backLength >= i)
		{
			if (backLength == 0) break;
			if (maxNum < strNum[++pos])
			{
				curPos = pos;
				maxNum = strNum[pos];
			}
			backLength--;
		}
		curPos++;
		ans.push_back(maxNum);
	}
	cout << ans << endl;
}

문제접근2

• 스택 을 이용하여 풀었다.
• 앞자리부터 숫자를 결정할 때 매번 내리는 선택이 최선의 선택이 되기 위해서는 가능한 한 큰 숫자를 앞에 위치할 수 있도록 해야 한다.
• 스택 자료구조는 내가 선택해 온 숫자들보다 더 큰 숫자를 만나게 되었을 때, 총합 최대 K번 만큼 pop 을 하여 앞에 위치하는 작은 숫자들을 제거하고 큰 숫자를 최대한 앞으로 위치시킬 수 있다.
• 주어진 숫자 문자열을 앞에서부터 탐색하며 현재 선택된 숫자와 스택의 top 에 위치한 숫자를 비교한다.
  1. top 에 위치한 숫자가 더 크고, 스택의 크기가 (N-K) 보다 작다면 push 한다.
  2. top 에 위치한 숫자보다 현재 선택된 숫자가 더 크다면, 현재 선택된 숫자보다 작은 숫자들을 최대한 스택에서 꺼내고, 현재 선택된 숫자를 push 한다.
  3. 이미 K번 pop 을 한 경우 현재 선택된 숫자를 push 한다.

  

구현

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

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

	int N, K;
	string strNum;

	cin >> N >> K;
	cin >> strNum;
	
	stack<char> s;
	int eraseCount = 0;
	int i = 0;
	string ans;
	for (int i = 0; i < strNum.length(); i++)
	{
		if (eraseCount == K)
		{
			s.push(strNum[i]);
			continue;
		}
		if (s.empty()) s.push(strNum[i]);
		else if (s.top() < strNum[i])
		{
			while (s.top() < strNum[i])
			{
				if (eraseCount == K) break;
				s.pop();
				eraseCount++;
				if (s.size() == 0) break;
			}
			s.push(strNum[i]);
		}
		else if (s.size() < N - K)
		{
			s.push(strNum[i]);
		}
	}

	while (!s.empty())
	{
		ans.push_back(s.top());
		s.pop();
	}
	
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
}