[Algorithm]Baekjoon 2812번 : 크게 만들기

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 
int n, k;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> k;
 
    vector<int> stack;
    char c;
    int tempK = k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> c;
        int num = c - '0';
 
        if (stack.empty())
        {
            stack.push_back(num);
        }
        else
        {
            if (num <= stack.back())
            {
                stack.push_back(num);
            }
            else
            {
                while (!stack.empty() && num > stack.back() && k > 0)
                {
                    --k;
                    stack.pop_back();
                }
                stack.push_back(num);
            }
        }
    }
    
    while (stack.size() > n - tempK)
    {
        stack.pop_back();
    }
 
    for (int i = 0; i < stack.size(); ++i)
    {
        cout << stack[i];
    }
}

 

스택의구조를 이용해서, 숫자를 넣다가 큰 숫자를 만나면 최대 k번만큼 스택의 top이 num보다 큰숫자일떄까지 pop한 후, num값을 푸쉬하면 된다. 나중에 출력하기 편하게하기위해 스택보단 벡터를 사용했다.

 

큰 숫자를 만드려면 앞쪽의 숫자일수록 최대한 값이 커야한다. 그렇기때문에 k번만큼의 삭제기회를 앞쪽에다가 배정한 느낌이다.

top이 num보다 작은 경우를 제외하곤 전부 스택에 push한다.

반복문이 끝난 후, 스택의 크기가 n - k보다 클 경우, 개수를 맞춰야하니 필요없는부분을 pop하고 출력해주면 된다.

 

자 여기서 조심해야 할 점은 다음과 같다.

n은 최대 '50만'자리의 숫자이다. 저 숫자전부를 하나의 변수에 담는건 불가능하다.

그렇기 때문에 각 자리의 숫자 한개씩 입력받아야 한다. 그래서 char형으로 입력받은 것이다.

출력할 때도 마찬가지로 한개씩 그대로 출력해주면 된다.