(2024-10-30) 2 문제 : 백준 - 2812 (크게 만들기)

 

숫자를 지워서 크게 만들려면, 앞자리의 수를 가장 크게 만들어야 한다.

즉 숫자를 앞자리부터 가능한 내림차순의 형태로 만드는 것이 가장 큰 숫자를 만드는 것이다.

 

예를 들자면, 129378 에서 2개의 숫자를 지운다면 1, 2를 지워 9378의 형태로 만드는 것이다. 여기서 1개를 더 지운다면 3을 지워 978의 형태로 만드는 것이 최대고, 하나를 더지운다면 7을 지워 98의 형태로 만드는 것이 최대값이다.

 

즉, 숫자를 가장 앞자리부터 하나씩 순회하며 앞의 숫자가 현재 숫자보다 작다면 앞의 숫자를 제거하는 것이다. 이를 위해 stack을 활용하였다.

 

문자열에서 그대로 삭제해버리면 시간 복잡도가 너무 커진다. 그러므로 문자열의 크기를 직접 변경하며 앞의 숫자를 제거하는 것이 아니라, stack에 숫자를 차례대로 삽입하고 삭제하며 바로 앞의 숫자를 빠르게 구하는 것이다.

 

그래서, 문자열에선 삭제된 문자를 'X'로 변경하고, 직전의 숫자는 stack을 통해 확인하도록 하였다. 문자를 하나 지울 때마다 카운팅을 하며, 지울 수 있는 최대 개수만큼 다 지웠다면 반복문을 종료해준다. 하지만, 최대 개수만큼 다 지우지 못하고 반복문이 종료되는 경우도 있다.

 

이러한 경우 마지막에 남은 삭제 개수만큼 숫자의 뒤에서부터 제거해준다. 왜냐하면, 반복문을 수행하며 지울수 있는 만큼 다 지웠다면 숫자는 이미 완벽한 내림차순의 형태일 것이다. (987653, 999999 이런 형태)

 

그렇다면, 앞의 숫자를 지우는 것보다 뒤의 숫자를 지우는 것이 더 큰 값을 만들기 때문에 뒤의 숫자를 지워야한다. 그렇게 모두 지운 다음, 문자열을 다시 순회하며 'X'가 아닌 숫자만 출력해주면 된다.

 

#include <iostream>
#include <vector>
#include <stack>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumLength = 0, DeleteCount = 0;
    std::cin >> NumLength >> DeleteCount;
    
    std::string Number = "";
    std::cin >> Number;
    
    std::stack<int> Indexs;

    for (int i = 0; i < NumLength; i++)
    {
        if (Indexs.size() == 0)
        {
            Indexs.push(i);
        }
        else
        {
            while(Indexs.size() > 0 && Number[Indexs.top()] < Number[i])
            {
                Number[Indexs.top()] = 'X';
                Indexs.pop();

                DeleteCount--;

                if (DeleteCount == 0)
                {
                    break;
                }
            }

            if (DeleteCount == 0)
            {
                break;
            }

            Indexs.push(i);
        }
    }

    while(Number.size() > 0 && DeleteCount > 0)
    {
        if (Number.back() != 'X')
        {
            DeleteCount--;
        }

        Number.pop_back();
    }

    for (int i = 0; i < Number.size(); i++)
    {
        if (Number[i] != 'X')
        {
            std::cout << Number[i];
        }
    }

    return 0;
}