크게 만들기

www.acmicpc.net/problem/2812

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	21627	5528	3984	25.650%

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

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

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #4 3번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: doju, engcraft

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 스택

추가 예제

https://hsin.hr/coci/archive/2011_2012/

예제 입력 A

11 3
67429495152

예제 출력 A

79495152

예제 입력 B

30 7
928857066163493066555730841879

예제 출력 B

98876693066555730841879

예제 입력 C

9 2
999991111

예제 출력 C

9999911

예제 입력 D

100 61
6617423282157290684025607883097699259905250470744165128706131448395502185407310941966307933122347117

예제 출력 D

999999955285407310941966307933122347117

K와 N의 범위 1 ≤ K < N ≤ 500,000 -> string 처리
N자리의 숫자가 주어졌을 때 N에서 K만큼 숫자를 제거
가장 큰 숫자를 찾는 것이 목적

실패한 로직과 코드

숫자의 처음 기준으로 제거 가능한 개수의 숫자만큼
인덱스 더한 범위 내에서 가장 큰 숫자를 기준으로 앞을 전부 제거
-> 만약 제거해야만 하는 숫자가 K의 범위보다 뒤에 있으면 잘못된 결과가 나온다. -> 망한 로직 

위의 알고리즘으로 2시간은 넘게 고민함
져서 다른 방법을 생각하지 못한다.

#include <iostream>
#include <string>

using namespace std;

int n, k;
char c;
string number = "";

void initalization()
{
	cin >> n >> k;

	int temp = n;
	while (temp > 0)
	{
		cin >> c;
		number.push_back(c);
		temp--;
	}
}

void test(int pivot, int k)
{
	if (k <= 0) { return; }
	
	int maxnumberidx = 0;
	int numbercheck = -1;
	cout << "시작 pivot : " << pivot << " 남은 지울 숫자 k : " << k << "\n";
	for (int i = pivot; i <= k + pivot; i++)
	{
		if (numbercheck < number[i] - '0')
		{
			numbercheck = number[i] - '0';
			maxnumberidx = i;
		}
	}
	
	cout << "가장 큰 수 : " << numbercheck << " 인덱스 번호 : " << maxnumberidx << "\n";

	if (k == number.length() - 1)
	{
		if (k == 1)
		{
			numbercheck = 10;
			cout << "numbercheck : " << numbercheck << " \n";
			cout << "pivot : " << pivot << " number.length() : " << number.length() << "\n";
			for (int i = pivot; i <= number.length() - 1; i++)
			{
				cout << numbercheck << " 비교 " << number[i] - '0' << "\n";
				if (numbercheck > number[i] - '0')
				{
					cout << " 점검 number[i] - '0' :  " << number[i] - '0' << "\n";
					numbercheck = number[i] - '0';
					maxnumberidx = i;

				}

			}


			cout << "-------------------------------------------------" << "\n";
			cout << "삭제 전 결과 : " << number << " maxnumberidx : " << maxnumberidx << "\n";
			number.erase(number.begin() + maxnumberidx, number.begin() + maxnumberidx + 1);
			cout << "삭제 후 결과 : " << number << "\n";
			cout << "-------------------------------------------------" << "\n";
			return;
		}
	}

	cout << "-------------------------------------------------" << "\n";
	cout << "삭제 전 결과 : " << number << "\n";
	number.erase(number.begin() + pivot, number.begin() + maxnumberidx);
	cout << "삭제 후 결과 : " << number << "\n";
	cout << "-------------------------------------------------" << "\n";
	test(pivot + 1, k - (maxnumberidx - pivot) );
}

int main()
{
	initalization();
	
	test(0, k);
	//cout << "n : " << n << " k : " << k << "  number : " << number << "\n";
}

다른 로직

통과된 코드

문제를 해결하는 알고리즘이 떠오르지 않아서 시간을 많이 소요

Stack 사용을 별로 해본 적이 없어서 문제 해결 방법에서 떠오르지 않았다.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<char> myStack;
int n, k;
char c;
string number = "";
string result = "";

void Initalization()
{
	cin >> n >> k;

	int temp = n;
	while (temp > 0)
	{
		cin >> c;
		number.push_back(c);
		temp--;
	}
}


int main()
{
	// 입력을 초기화 해주는 함수
	Initalization();
	
	// 처음 시작을 위해 하나 넣어준다.
	myStack.push(number[0]);

	for (int i = 1; i < number.length(); i++)
	{
		// 제거 가능한 수가 0 이면 스택에 넣고 넘어간다. 
		if (k == 0)
		{
			myStack.push(number[i]);
			continue;
		}
		
		// 만약 스택의 숫자보다 비교 숫자보다 크다면 
		// 스택의 숫자를 제거하고 다시 스텍의 수와 비교
		// 스텍이 비거나 비교 숫자보다 크거나 같으면 
		// 비교 숫자를 스택에 넣어준다.
		if (myStack.top() < number[i])
		{

			while (myStack.top() < number[i] && !myStack.empty() && k > 0)
			{
				myStack.pop();
				k--;
				if (myStack.empty())
				{
					break;
				}
			}

			myStack.push(number[i]);
		}
		else if (myStack.top() >= number[i])
		{ 
			// 만약 스택의 숫자보다 비교 숫자보다 크다면 
		    // 숫자를 스택에 넣어준다.
			myStack.push(number[i]);
			continue;
		}
	}

	// 모든 숫자를 전부다 비교해도 제거 가능한 숫자가 남으면
	// 그 수만큼 스택에서 제거한다.
	while (k > 0)
	{
		myStack.pop();
		k--;
	}

	while (!myStack.empty())
	{
		result.push_back(myStack.top());
		myStack.pop();
	}

	// 반대로 출력 되므로 뒤집어준다.
	string resultReverse(result.rbegin(), result.rend());
	cout << resultReverse;
}