[Programmers/C++] 큰 수 만들기

시간 복잡도

• 스택을 이용하여 $O(N)$ 만큼의 시간이 발생합니다.

문제 접근법

1. 스택이 비어있다면 숫자를 스택에 삽입합니다.
2. 스택이 비어있지 않다면 스택이 비거나 k가 0보다 크고 스택의 top에 있는 숫자가 현재 숫자보다 크거나 같을 때 까지 제거합니다.
3. 이후 스택에 현재 숫자를 삽입합니다.
4. 위의 과정이 끝난 후 k가 0보다 크다면 해당 개수만큼 스택에서 제거합니다.
5. 스택의 숫자들을 꺼내고 역순으로 만들어줍니다.

코드

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

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    stack<char> s;
    
    for(int i=0; i<number.size(); i++)
    {
        if(s.empty())
            s.push(number[i]);
        else
        {
            while(!s.empty() && k>0)
            {
                if(s.top() < number[i])
                {
                    k--;
                    s.pop();    
                }
                else
                    break;
            }
            s.push(number[i]);
        }
    }
    
    while(!s.empty() && k>0)
    {
        s.pop();
        k--;
    }
    
    while(!s.empty())
    {
        answer+=s.top();
        s.pop();
    }
    
    reverse(answer.begin(), answer.end());
    
    return answer;
}