[백준,c++] 2812번 - 크게 만들기

문제

2812번: 크게 만들기

 

코드

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, K; cin>>N>>K;
    string num; cin>>num;
    stack<char> st;
    int remove_cnt = 0;
    int i=0;
    
    for(i; i<N; i++){
        if(st.empty()) st.push(num[i]);
        else if(st.top()>num[i]) st.push(num[i]);
        else{
            while(true){
                if(!st.empty() && num[i]>st.top()){
                    if(remove_cnt == K) break;
                    st.pop();
                    remove_cnt++;
                }
                else break;
            }
            st.push(num[i]);
        }
    }
    

    string ans = "";
    while(!st.empty()){
        ans += st.top();
        st.pop();
    }
    reverse(ans.begin(), ans.end());
    ans = ans.substr(0, N-K);
    cout<<ans;
}

 

풀이

stack을 활용하여 해결했습니다.

1. 이전의 숫자보다 현재의 값이 크다면 현재보다 가장 큰 값이 나오기 전까지 스택의 모든 값들을 지웁니다.
2. 이전의 숫자가 현재의 값보다 크다면 현재의 값을 추가합니다.
3. 스택의 문자열을 0, n-k 길이까지 출력합니다.

이미 k개를 제거했음에도 불구 하고 3번 작업을 하는 이유는 아래와 같이 크기가 같은 숫자만 있어서 전부 스택에 push 될 경우가 있기 때문입니다.

2 1
1 1