[프로그래머스 Lv.2] 큰 수 만들기

[풀이]

https://school.programmers.co.kr/learn/courses/30/lessons/42883

 

[문제]

 

입력 값이 크기 때문에 단순한 이중 반복문으로는 풀 수 없다. 풀이 방식은 오큰수 개념을 활용했다.여기서의 동작은 뒤의 숫자가 클 때 앞의 숫자를 제거하는 방식으로 구현되어있다.

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

using namespace std;

// 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수
// ex) 1924에서 두 개 제거하면 19, 12, 14, 92, 94, 24가 만들어지는데, 이 중 가장 큰 수는 94
// number : 2자리 이상, 1'000'000 이하
// k : 1 이상 number 자릿수 미만 자연수
string solution(string number, int k)
{
    string answer = "";
    stack<char> Stk;

    // 오큰수 전략(앞큰수로 k개 제거하기)
    for (char digit : number)
    {
        // 뒤의 숫자가 클 때 앞의 숫자를 제거
        while (!Stk.empty() && k > 0 && Stk.top() < digit)
        {
            Stk.pop();
            k--;
        }
        Stk.push(digit);
    }

    // 아직 k가 남아있다면 뒤에서 제거
    while (k-- > 0)
    {
        Stk.pop();
    }

    // 스택 → 문자열로 변환
    while (!Stk.empty())
    {
        answer += Stk.top();
        Stk.pop();
    }

    reverse(answer.begin(), answer.end());
    return answer;
}