[백준문제풀이] 2812 크게 만들기

 

풀이일시 : 2020-09-10

​

 

문제 :

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

​

 

입력 :

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

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

ex)

4 2

1924

​

 

출력 :

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

ex)

94

​

 

풀이 :

그리디알고리즘

숫자의 자리를 바꾸면 안된다.

단순히 앞에서부터 숫자를 읽어가면서 스택에 넣으면 된다. 다만 새롭게 등장한 뒤에있는 숫자보다 작은 숫자들을 모두 스택에서 빼는 과정을 거쳐 스택에는 오직 큰 숫자들만 넣어주면 된다.

스택에 다 넣은 뒤에도 지워야되는 숫자가 있다면? -> 뒤에서부터 원하는 자리수대로 뽑으면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, k;
string a;
vector<char> result;

int main() {
	cin >> n >> k >> a; // N자리 숫자, K개를 지우는 것 a숫자
	int i = 0;
	while (i != a.size()) {
		while (k != 0 && !result.empty() && result.back() < a[i]) {
			result.pop_back(); //들어간 값이 있던값보다 작으면 있던값을 result에서 꺼낸다.
			k--; //k개만 지우면 되므로
		}
		result.push_back(a[i]); //result에 넣는다.
		i++;
	}
	while (k--) { //k가 다 안지워졌다면 나머지를 지워주는것
		result.pop_back(); //pop_back으로 꺼내지않고 담겨있는 그대로 0부터 출력한거
	}
	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}
}

 

참고자료 : vector container

dbstndi6316.tistory.com/25

[개념정리] vector container