[백준] 2812 크게 만들기, C++

2812번: 크게 만들기

문제 요약

주어진 길이 N의 숫자에서 K개를 제거해서 가장 큰 수를 만들어야함

접근

1.

앞에 있을수록 9에 가까워야하고 뒤에 있을수록 0에 가까워야한다고 생각이 들었다.
하지만 K가 작으면 만들기기 어렵다고 생각이 들었다.
이쯤 도저히 머리가 안돌아가서 힌트를 봤다.
스택을 사용하라고 되어있어서 어떻게 풀어야할지 고민을 꽤 했다.
그러다가 갑자기 스택에 넣고 뺄때 비교하면 될거같다고 생각이 들었다.

스택의 최상위 값이랑 index 가 가리키는 값을 비교해서 최상위 값이 크거나 같을때까지 스택에서 pop하고, K 개의 원소를 뺄 때까지 계속 반복한다.
더이상 뺄 아이템이 없으면(모든 값이 같은 경우) 남은 개수만큼 뒤에서 뺀다.

알고리즘

1. stack이 비어있으면 현재 인덱스 값 push
2. 값이 있으면 stack.top() 과 현재 인덱스 값 비교
   1. stack.top < number[cur_index] 이면 stack.pop()
   2. stack이 비거나 stack.top >= number[cur_index] 일때까지 반복
   3. 스택에서 빼낸 개수가 K개면 반복문 종료
3. 스택에 넣은 값으로 문자열 만들고 남은 문자열 붙이기
   1. 반복

전체 코드

#include <iostream>
#include <stack>
#include <string> // string
#include <algorithm> // reverse

using namespace std;

int N, K;
string strNumber;

void check()
{
    int break_i = -1;
    string tmpStrNumber;
    stack<char> s;
    for (int i=0; i<N; i++) // char ch
    {
        char ch = strNumber[i];
        if (s.empty())
        {
            s.push(ch);
            continue;
        }

        while (!s.empty())
        {
            if (s.top() < ch)
            {
                s.pop();
                K--;
                if (K == 0)
                {
                    break_i = i;
                    break;
                }
            }
            else
            {
                break;
            }
        }

        if (K == 0)
        {
            break;
        }
        s.push(ch);
    }
    // stack -> tmpStrNumber
    while(!s.empty())
    {
        tmpStrNumber += s.top();
        s.pop();
    }
    reverse(tmpStrNumber.begin(), tmpStrNumber.end());
    if (break_i != -1)
    {
        for (int i = break_i; i < N; i++)
        {
            tmpStrNumber += strNumber[i];
        }
    }
    // renew strNumber, N
    strNumber = "";
    for (size_t i = 0; i < tmpStrNumber.size() - K; i++)
    {
        strNumber += tmpStrNumber[i];
    }
    return;
}

int main()
{
    cin >> N >> K;
    cin >> strNumber;

    check();

    cout << strNumber << endl;

    return 0;
}

새로 알게된 것

1. string에도 rbegin, rend 라는 reverse_iterator 가 있다. 이번엔 algorithm헤더에 있는 reverse 함수를 사용했지만 나중에 역순으로 접근할때 사용해볼듯하다.