백준 2812 - 크게 만들기

문제 설명

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 길이가 N인 숫자가 주어졌을 때 K개의 숫자를 제거해 가장 큰 수를 만들면 된다.

 

시간을 제외하고 풀이를 생각해 보면 K개의 숫자 조합을 만들고 이를 제거해 보며 최댓값을 구하면 된다.

하지만 N, K가 최대 500,000이기 때문에 시간 초과가 발생할 것이다.

따라서 다른 전략이 필요하다.

 

우선 가장 큰 수를 만들기 위해서는 왼쪽(앞쪽)수가 커야 한다.

따라서 앞에서 부터 가장 큰 수를 선택하면 된다.

예를 들어 보자.

4 2
1924

 1은 앞에 아무 것도 없기 때문에 선택할 것이다.

9를 선택할지 결정할 때 1을 제거하고 9를 선택하는 것이 가장 큰 수를 만드는 방법이다.

그리고 2를 선택할 때는 일단 선택을 해야 한다.

2를 검사할 때는 뒤에 어떤 수가 있는지 모르기 때문이다.

4를 선택하는 상황에서는 2를 제거하고 4를 선택하는 것이 정답이 된다.

따라서 i번째 수를 포함할지 결정할 때 i번째 수보다 앞의 수가 작다면 제거하면 된다.

이때 제거하는 수를 K에서 빼주며 K번만 뺄 수 있게 하면 된다.

 

한 가지 의문이 들 수 있는 부분이 있는데 앞에서 수를 제거하지 않는 경우 최적해가 나올 수 있지 않을까 생각할 수 있다.

하지만 앞에서 작은 수를 선택하면 뒤에 9999로 아무리 큰 수를 선택해도 앞이 작아 결국 작은 수가 완성된다.

따라서 그리디하게 앞에서부터 최대한 큰 수를 선택하는 것이 정답이 된다.

 

이를 구현하기 위해서는 스택의 개념을 이용하면 된다.

i번째 수보다 스택에 top에 있는 수가 작다면 하나씩 제거하면 된다.

int num = input[i] - '0';
while (K > 0 && !temp.empty() && temp.back() < num)
{
    temp.pop_back();
    K--;
}

마지막으로 주의할 점은 N이 500,000이기 때문에 int, long long으로 표현이 불가능하다.

따라서 정답을 string으로 구성해야 한다.

string ans;
for (int i = 0; i < temp.size(); i++)
{
    ans += temp[i] + '0';
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, K;
string input;

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

	vector<int> temp;
	for (int i = 0; i < N; i++)
	{
		int num = input[i] - '0';
		while (K > 0 && !temp.empty() && temp.back() < num)
		{
			temp.pop_back();
			K--;
		}

		temp.push_back(num);
	}
		
	while (K > 0)
	{
		K--;
		temp.pop_back();
	}

	string ans;
	for (int i = 0; i < temp.size(); i++)
	{
		ans += temp[i] + '0';
	}

	cout << ans;
}

---