프로그래머스 큰 수 만들기 C++

 

처음 풀이

#include <string>
#include <vector>

using namespace std;

// 1 2 9 2 3 4
string solution(string number, int k) {
    string answer = "";
    
    // 앞자리 수 < 뒷자리 수 라면, 제거하면 됨. 이게 최선이네.
    // 근데 제거하고 다시, 제거하고 다시 이렇게 하면 시간초과니까
    // 한번에 제거할거 다 찾고 한번에 제거해야함
    
    // 또는 제거할거를 따로 넣기보다, 제거할거만 남겨두고 새로 만들기
    
    int len = number.length();
    int counter = 0;
    for(int i = 0; i < len; i++) {
        
        if(counter < k && i + 1 < len && number[i] < number[i + 1]) {
            counter++;
        } else {
            answer += number[i];
        }

    }
    
    return answer;
}

예외케이스

이걸 보고, STACK 같은걸 써야겠구나 싶었다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    stack<char> ans;
    
    int len = number.length();
    int counter = 0;
    
    for(int i = 0; i < len; i++) {
        
        while(!ans.empty() && counter < k && ans.top() < number[i]) {
            ans.pop();
            counter++;
        }
        
        ans.push(number[i]);
    }
    
    // 4321 같은 내림차순의 경우, 이 과정에서 뒤에서부터 제거해줘야함.
    while(!ans.empty()) {
        
        if(counter++ < k) {
            ans.pop();
        } else {
            answer += ans.top();
            ans.pop();
        }
    }
    
    reverse(answer.begin(), answer.end());
    return answer;
}