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

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

2812번: 크게 만들기

 

[문제 요약]

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

 

[문제 조건]

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

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

- 시간 제한 : 1초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제가 아주 심플에서 좋다.

 

예로들어 문제를 설명하자면 7자리수 1231234가 있을때 여기서 몇개의 수를 제거하여 나머지를 합쳤을때 가장 큰 수가 나오면된다.

 

처음에는 그냥 작은 수 먼저 제거하면 큰 수가 되겠지 생각했지만 391123 여기서 2개를 제거했을때 작은 수 부터 제거하면 3923이 되지만 정답은 9123이 된다.

 

그래서 필자는 다른 간단한 아이디어에서 출발했다.

 

먼저 큰 수를 만들려면 작은수들을 제거하는건 맞는거 같은데 어디에 있는 작은 수를 제거해야될지 고민을 했다. 그래서 생각했던 방법이 큰 수 앞에 있는 작은 수들을 제거하면 되지 않을까? 라는 생각이 문득 떠올랐다.

 

그래서 이 방법을 위의 예제 391123에 적용 시켜봤다.

 

방법을 자세히 설명하면

• 주어진 숫자를 앞에서 부터 스택에 집어넣는다.
• 숫자를 집어넣을때 집어넣는 수보다 작은 숫자들은 전부 제거하는데 이 횟수는 K를 넘지 않는다.

이 과정을 반복해주고 나머지 숫자들을 순서대로 출력해주면된다.

 

대충 그림으로 그려보면 이렇다

3이 들어가있는 상태에서 9를 집어넣으려 할때 3보다 9가 더 크니 3을 제거하고 9를 집어넣는다.

911이 들어가있는 상태에서 2를 집어넣으려 할때 1보다 2가 더 크니 1을 제거한다. 여기서 제거할 수 있는 수의 제한에 도달했으니 나머지 숫자들을 전부 집어넣고 출력하면된다.

 

출력할때 주의할점은 길이가 처음에 주어지는 문자열의 길이가 최대 50만이기때문에 출력할때도 string으로 해주는게 안정적이다. (다른 자료형으로 되나....?)

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

unsigned long long N, K;
stack<unsigned long long> stk;
string tmp;

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

	cin >> N >> K;
	cin >> tmp;

	for (int i = 0; i < tmp.size(); i++)
	{
		int num = tmp[i] - '0';
		while (!stk.empty() && stk.top() < num && K != 0)
		{
			stk.pop(); K--;
		}
		stk.push(num);
	}

	for (int i = 0; i < K; i++) stk.pop();

	string ans;
	while (!stk.empty())
	{
		ans.push_back(stk.top() + '0');
		stk.pop();
	}
	reverse(ans.begin(), ans.end());
	cout << ans;
}

 

굳