[백준] 2812 | 크게 만들기 | C++

내가 생각한 풀이의 핵심은 이렇다.

 

입력으로 주어진 숫자를 하나씩 순서대로 처리한다:
    만약 i번째 수 > stack의 top이라면:
        stack pop;
        k 하나 감소;
    i번째 수를 stack에 넣는다;

 

이후 k가 남아있을 수 있으니,

k가 0이 될 때까지 stack을 pop시켜야 한다.

(나중에 다른 사람의 풀이를 통해 알게 되었다.)

 

그리고 stack에 담긴 수를 역순으로 꺼내서 답을 조합하였다.

 

그런데 stack으로 풀면 시간 초과가 났다.

그래서 vector로 대신하여 풀었더니 맞았습니다!!가 나왔다. (왜 이런지는 잘 모르겠다.)

 

---

 

정답 소스코드 - vector를 이용한 풀이

 

#include<iostream>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, k;
    string inp;
    vector<char> res;
    cin>>n>>k;
    cin>>inp;

    for(int i=0; i<inp.size(); i++) {
        while(res.size()>0 && inp[i]>res.back() && k>0) {
            k--;
            res.pop_back();
        }
        res.push_back(inp[i]);
    }
    while(k>0) {
        k--;
        res.pop_back();
    }

    for(int i=0; i<res.size(); i++) cout<<res[i];
    return 0;
}

 

시간 초과 소스코드 - stack을 이용한 풀이

 

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, k;
    string inp, res="";
    stack<char> stk;
    cin>>n>>k;
    cin>>inp;

    for(int i=0; i<inp.size(); i++) {
        while(!stk.empty() && inp[i]>stk.top() && k>0) {
            k--;
            stk.pop();
        }
        stk.push(inp[i]);
    }
    while(!stk.empty() && k>0) {
        k--;
        stk.pop();
    }
    while(!stk.empty()) {
        res=stk.top()+res;
        stk.pop();
    }

    cout<<res<<"\n";
    return 0;
}