[C++/PGS] Lv.2 : 큰 수 만들기 (GREEDY) - retry

 

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=cpp

 

 

다시풀어보기 시리즈....

3년전에 어찌저찌 풀었던 문제인데

도대체 어떻게 풀었던건지 기억이 안 남. 너무 어렵게 풀었던데 왜 이랬을까..?

 

https://xxilliant.tistory.com/103

[C++/PGS] Lv.2 : 큰 수 만들기 (GREEDY)

 

 

이번에는 가장 정석 방법인 스택으로 해결했다.

Stack에 넣으려는 숫자를 기존 stack에 있는 숫자들과 비교하는 로직이다!

그리디 알고리즘 넘 어렵다 ㅠ,ㅠ

 

나의 풀이

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> st;
    st.push(number[0]);
    int cnt = 0; // 제거하는 숫자를 k개까지 카운트
    for(int i = 1; i < number.length(); ++i){
        while(cnt<k && !st.empty() && st.top()<number[i]){
            st.pop();
            cnt++;
        }
        st.push(number[i]);
    }
    while(cnt<k && !st.empty()){
        st.pop();
        cnt++;
    }
    while(!st.empty()) {
        char a = st.top();
        answer += a;
        st.pop();
    }
    reverse(answer.begin(), answer.end());
    return answer;
}