[C++/백준] 2812번-크게 만들기

링크

---

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

문제

---

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

입력

---

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

---

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

풀이

---

무조건 높은자리수에 있는 숫자가 커야 가장 큰 수를 만들 수 있으므로 9가 아니라면 지울 수 있는 개수만큼 뒤의 숫자들을 검사하고 가장 큰 수를 넣는다. 넣은 수 앞의 부분은 결과에 넣지 않는다.

속도 향상을 위해 0인 경우와 9인 경우는 따로 조건문을 만들었다.

코드

---

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

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

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

	string num;
	cin >> num;

	string result = "";

	for (int i = 0; i < N; i++) {
		if (result.length() == N - K)
			break;
		int x = 0;
		if (K == 0)
			result += num[i];
		else {
			if (num[i] == '9') {
				result += num[i];
			}
			else if (num[i] == '0') {
				K--;
				continue;
			}
			else {
				for (int j = 1; j <= K; j++) {
					if (num[i + x] < num[i + j]) {
						x = j;
						if (num[i + j] == '9')
							break;
					}
				}
				if (x == 0 && i == N - 1 && K == 1)
					break;
				result += num[i + x];
				K -= x;
				i += x;
			}
		}
	}
	cout << result;

	return 0;
}