큰 수 만들기

코드

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

string solution(string number, int k) {
    string answer = "";
    int n_length = number.length() - k, i=0;
    stack<char> s;
    s.push(number[i++]);
    /* stack을 이용한 풀이 */
    while(i < number.length())
    {
        char ch = s.top();
        /* "현재 top에 있는 수 < 들어오는 수" 인 경우에 s.top() >= 들어오는 수 될 때 까지 pop!  */
        if(ch < number[i]){
            /* 원하는 만큼 삭제 후에는 더 이상 삭제하면 안됨!  k>0 중요! */
            while(!s.empty() && k>0)
            {
                if(s.top() >= number[i])  break;
                s.pop();
                k--;
            }
        }
        s.push(number[i++]);
    }
    /* 99991 처럼 같은 수가 연속될 경우 개수 맞춰서 빼주면 된다 - 예외 처리 */
    while(s.size() != n_length) s.pop();

    /* 출력 형식 만들기 */
    while(!s.empty())
    {
        answer = s.top() + answer;
        s.pop();
    }
    return answer;
}

• key point!
  1) 내가 stack에 넣어 놓은 수 (s.top()) 보다 지금 읽는 수(number[i])가 더 크다면 앞으로 와야함
     --> 그 순간 순간에 최적인 경우를 선택하는 것임 (그때 그때 큰 수를 선택!)
        --> Greedy algorithm