(C++) 백준 2812번 크게 만들기

1. 링크

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

2. 풀이

고찰

stack library 쓰면 시간초과 나옴 ㅠㅠ
다른코드 확인했을때도 stack으로 푼 경우는 없는거같다
어차피 stack자체가 배열로 쉽게 구현할 수 있으니까
stack은 따로 라이브러리 쓰지 않는게 나은듯?

코드

문제 아이디어는 내 앞에 나보다 큰 수는 올 수 있음 / 작은 수는 올수 없음 이다.
앞자리 부터 스택에 차례대로 넣으면서 가장 위에 있는 수가 나보다 큰지 작은지 비교하며
작으면 큰 수가 나올때 까지 pop한다.

문제에서 주어진 Test Case는 간단하게 풀 수 있다

4 2
1924

(1) element 1 : stack empty → stack [1]
(2) element 9 : 9 앞에 더 작은 수 1은 올 수 없으므로 pop 하고 push(9) → stack [9]
(3) element 2 : stack push 2 → stack [9] [2]
(4) element 4 : 4 앞에 더 작은 수 2는 올 수 없으므로 pop 하고 push(4) → stack [9] [4]

하지만 위 경우는 가장 간단한 경우이고 ...많은 예외 덕분에 디버깅할 시간이 많이 필요했다
당연함 ..나는 아직 모자람 ....(˘̩̩ε˘̩ƪ)
암튼 내가 생각하기에 관건이었던 것은 입력받은 값 만큼 for문을 돌면서 위 과정을 수행해야 한다는 것!

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

char st[500005];

int main(){
	 
	memset(st, '0', sizeof(st));
	
	int N,K;
	cin>>N>>K;
	
	string input;
	cin>>input;	
	 
	int len = N-K;
	int top = 0;
	
	for (int i=0; i<N; i++){ 
	
	if(K){  
		if (top==0) {  
			st[top] = input[i];
			top++;
			continue;}
		 
		if (st[top-1]<input[i]){  
			while(top>0 && st[top-1]<input[i] && K>0) {  
			st[top-1]='0';
			top--;
			K--; 
			}
			st[top]=input[i];
			top++;
			}
			
		 
		else {
			st[top]=input[i];
			top++;
		}
			
	}
	
	// K==0
	else { 
			st[top] = input[i]; 
			top++; } 
		
	}	
	 
	
	for (int i=0; i<len; i++) cout<<st[i];
	
}