크게 만들기
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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번
알고리즘 분류
추가 예제
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;
}
