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

2812. 크게 만들기

2812번: 크게 만들기

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

간단해보이지만, 접근하는 과정이 엄청 어려웠다. 정말 스택은 상상도 못했고...

 

처음 접근한 방법은... 단지 예제를 보고 출력으로 나올 수 있는 알고리즘을 머리로 계산해보았다.

input =>
10 5
4177252841

 

 

1. 제외할 수 있는 앞쪽 수 4 1 7 7 중 가장 큰 수 앞에 있는 수들은 모두 제거해준다. (가장 앞자리 수가 크기 위함)

77252841

 

2. 현재 수가 다음 수보다 작다면, 그 수를 제외해준다. 앞의 수를 크게 유지하기 위함

77252841
=> 7752841
=> 775841

 

3. 제거 횟수가 남았다면, 뒷자리부터 차례대로 없애준다.

775841
=> 77584

 

이렇게 알고리즘을 짜고, 코드까지 짜봤었지만... 결과는 시간 초과였다.

그래서 힌트를 얻으려고 봤던 알고리즘 분류

스택이 엉뚱하게 껴있었지만... 곧 엉뚱이 아니라는 것을 깨달았다.

순서대로 각 자리 숫자를 스택에 넣어줄 때, 스택의 top과 비교해서 top보다 작다면 그냥 넣어주고, 크다면 pop을 해주고 push를 해주는 것이다!!!

 

그렇게 되면, 앞 자리를 크게 유지할 수 있게 된다.

이 과정을 거쳐도 제거 횟수가 남아있다면, 아까의 알고리즘처럼 뒷자리부터 차례대로 없애주면 된다.

 

전체 코드

 

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;


int main()
{
    int len, eraseCount = 0;
    cin >> len >> eraseCount;

    string str;
    stack<char> stack;
    cin >> str;

    for (int i = 0; i < static_cast<int>(str.size()); i++)
    {
        // 들어온 수를 앞과 계속 비교해
        // 앞의 수가 작다면 계속 지운다
        while (!stack.empty() && stack.top() < str[i] && eraseCount > 0)
        {
            stack.pop();
            eraseCount--;
        }

        stack.push(str[i]);
    }

    // 지우지 못했다면 뒤에서부터 지워준다
    while (eraseCount-- > 0)
    {
        stack.pop();
    }

    int size = static_cast<int>(stack.size());
    str = "";

    // 스택을 string으로 옮긴다
    for (int i = 0; i < size; i++)
    {
        str.push_back(stack.top());
        stack.pop();
    }

    // 거꾸로
    reverse(str.begin(), str.end());

        cout << str;

}

스택은 상상도 못했던 문제... 너무 쉽게 힌트를 본 것 같아서 좀 양심에 찔리기도 한다.

 

저런 힌트를 보지 않고도 머리로 생각해낼 수 있는 사고력을 키우고 싶다.