[BOJ] 크게 만들기 2812번 C++

 

문제

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

입력

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

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

출력

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

 

접근 방식

 

문제 자체는 간단하지만 꽤나 시간이 걸린 문제다

입력 데이터가

 

7 3 
1231234

 

위와 같다면 답은 3234가 나와야하는데

매커니즘은 다음과 같다

 

먼저, 스택이 비어있다면 스택에 숫자를 추가한다

스택이 비어있지 않다면 스택의 top을 확인하면서 현재 값보다 큰 top이 나타날때까지 카운트를 증가하면서 (이때 카운트값이 K보다 크면 안됨) pop을 해준다

 

여기서 주의할 점은

3 1
321

입력데이터가 다음과 같을 때 이다

이 값으로 하면 stack에서 pop이 일어나지 않는다

 

따라서 다시한번 cnt 값을 확인해 stack에서 K만큼 pop 해주어야 한다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N,K;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>K;
    string num; cin>>num;

    stack<char> st;
    int cnt = 0;
    for(int i=0; i<N; i++) {
        while(!st.empty() && cnt < K && st.top() < num[i]) {
            st.pop();
            cnt++;
        }
        st.push(num[i]);
    }
    while(cnt < K) {
        cnt++;
        st.pop();
    }
    stack<char> ans;
    while(!st.empty()) {
        ans.push(st.top());
        st.pop();
    }
    while(!ans.empty()) {
        cout<<ans.top();
        ans.pop();
    }
}