문제

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

입력

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

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

출력

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

---

1. 해결방법 및 소스코드

• 큐(Queue)와 스택(Stack)을 활용하였다.
• 우선, N이 최대 500,000인데 5십만자리 수는 기본적인 자료형으로 표현할 수 없으므로 수를 문자열로 받는다.
  char형으로 받은 수를 x라고 하면 x-'0'으로 정수로 변환할 수 있으므로 변환한 정수를 큐에 넣는다.
• 최종적으로 다룰 결과는 result라는 스택에서 완성된다. result스택에 우리가 받은 수(큐)에서 가장 앞자리수
  (number.front())를 추출(pop)하여 스택에 쌓음으로서 본격적인 풀이를 할 준비가 완료된다.

#include <iostream> #include <stack> #include <queue> #include <vector> using namespace std; int main() { int N, K; int resultsize; stack<int> result; queue<int> number; scanf("%d %d", &N, &K); char numstring[N + 1]; scanf("%s", numstring); int print_result[N]; for (int i = 0; i < N; i++) { number.push(numstring[i] - '0'); } //스택에 N자리 숫자의 맨 앞자리를 넣어주며 시작 result.push(number.front()); number.pop();

• 큐에서 한 번 pop을 해주었기 때문에 큐의 맨 앞에는 N자리 숫자의 두번째 숫자가 와 있다.
• 이제 number 큐에서 하나씩 pop을 해주면서 큐가 empty될 때까지 아래의 연산을 반복하면 된다.
  1. number.front() > result.top()인 경우에는 result 스택에서 number.front()보다 작은 값이 없을 때까지 result 스택을 pop해준다. 당연히 pop 한번에 K도 하나씩 감소시킨다. 이 때 반복적인 pop의 조건은 result스택이 비어있으면 안되고, K > 0임이 함께 보장되어야한다.
  2. 위 1번 조건에 만족하지 않거나 1번 조건에서의 반복적인 pop을 마무리해준 후, 그때서야 number.front()를 result 스택에 push 할 수 있게된다.
  3. 위 1, 2번 조건을 모두 마쳤으나 K가 아직 남아있을 수 있다. 이럴 경우에는 남은 K만큼 result 스택을 pop 해주고 K를 완전 소모시킨다.

// N자리 숫자의 2번째자리 숫자부터 검사 시작 while (!number.empty()) { int numberfront = number.front(); // printf("numberfront: %d\n", numberfront); if (numberfront > result.top()) { while (!result.empty() && (numberfront > result.top()) && K > 0) { // printf("%d를 pop합니다!\n", result.top()); result.pop(); K--; } } // printf("%d를 push합니다!\n", numberfront); result.push(numberfront); number.pop(); } //그럼에도 남은 K가 있다면 싹다 정리 while (K > 0) { result.pop(); K--; }

• 이제 result 스택의 사이즈를 알아낸 후, result 스택에서 남아있는 결과값을 프린트 해 줄 print_result 배열에 result 스택의 수를 옮겨담고, 결과를 출력한다.

resultsize = result.size(); for (int i = result.size() - 1; i >= 0; i--) { // printf("인덱스 %d 에 %d 저장\n", i, result.top()); print_result[i] = result.top(); result.pop(); } for (int i = 0; i < resultsize; i++) { printf("%d", print_result[i]); } printf("\n"); }

2. 전체 소스코드

#include <iostream> #include <stack> #include <queue> #include <vector> using namespace std; int main() { int N, K; int resultsize; stack<int> result; queue<int> number; scanf("%d %d", &N, &K); char numstring[N + 1]; scanf("%s", numstring); int print_result[N]; for (int i = 0; i < N; i++) { number.push(numstring[i] - '0'); } //스택에 N자리 숫자의 맨 앞자리를 넣어주며 시작 result.push(number.front()); number.pop(); // N자리 숫자의 2번째자리 숫자부터 검사 시작 while (!number.empty()) { int numberfront = number.front(); // printf("numberfront: %d\n", numberfront); if (numberfront > result.top()) { while (!result.empty() && (numberfront > result.top()) && K > 0) { // printf("%d를 pop합니다!\n", result.top()); result.pop(); K--; } } // printf("%d를 push합니다!\n", numberfront); result.push(numberfront); number.pop(); } //그럼에도 남은 K가 있다면 싹다 정리 while (K > 0) { result.pop(); K--; } resultsize = result.size(); for (int i = result.size() - 1; i >= 0; i--) { // printf("인덱스 %d 에 %d 저장\n", i, result.top()); print_result[i] = result.top(); result.pop(); } for (int i = 0; i < resultsize; i++) { printf("%d", print_result[i]); } printf("\n"); }