[BOJ] 크게 만들기_2812 C++ 풀이

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

접근 방법

먼저 N자리 숫자를 배열 형태로 입력받기 위해 문자열형을 사용하여 입력 받았다. string num;

숫자 K개를 지워서 가장 큰 수를 구하는 가장 단순한 방법은 N자리의 숫자중 가장 큰 수를 가능한 제일 앞에 위치하게 하는 것다.

즉, 지운 숫자의 갯수를 유의하며 입력받은 N개의 숫자의 첫째자리 부터 스택에 삽입해 가며 아래의 과정을 수행한다.

1. 스택의 top < num의 i번째 자리 수 $($num[i]) 스택의 top이 num[i]보다 크거나 같을때 까지 스택 top을 pop$($숫자 지우기). 그후 num[i]를 스택에 push.

for(int i=1; i<num.size(); i++)
{
    while(!st.empty() && st.top() < num[i])
    {
        if(cnt>=k) break;
        st.pop();
        cnt++;
    }
    st.push(num[i]);
}

이 과정을 통해 스택의 하단부터 지울수 있는 수를 고려한 가장 큰 수 순으로 수들이 정리된다.

1. 지워야 하는 수가 남았을땐 $($cnt < k), 이미 스택의 하단부터 가능한 큰 수들이 정렬되어 있기 때문에 스택의 top부분을 pop 해주면 된다.

스택에 정리되어있는 수의 출력을 위해서 st 스택의 수들을 res 스택에 옮겨 담은후 출력해 준다.

while(cnt<k) // 꼬리부분 자르기
{
    st.pop();
    cnt++;
}

구현

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

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    int cnt = 0; // 몇번 지웠는지 카운트
    string num;
    stack<char> st, res;// 출력을 위한 스택 - res

    cin>>n>>k;
    cin>>num;

    st.push(num[0]);

    for(int i=1; i<num.size(); i++)
    {
        while(!st.empty() && st.top() < num[i])
        {
            if(cnt>=k) break;
            st.pop();
            cnt++;
        }
        st.push(num[i]);
    }

    while(cnt<k) // 꼬리부분 자르기
    {
        st.pop();
        cnt++;
    }

    while(!st.empty()) // 출력을 위해 옮겨 담기
    {
        res.push(st.top());
        st.pop();
    }

    while(!res.empty())
    {
        cout<<res.top();
        res.pop();
    }

    return 0;
}

BOJ_크게 만들기