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

문제

백준 2812

2812번: 크게 만들기

풀이

N자리 숫자에서 K개만큼을 꺼내 줘야 합니다.

예제 입력 3의 경우를 보겠습니다.

10 4

4177252841

10자리 숫자에서 4자리를 제거해 가장 큰 숫자를 만들어야 합니다.

스택이 비지 않았고, 꺼낼 수 있으며, 현재 넣을 수가 stack의 top보다 클 때 stack을 pop 하고, cnt를 증가시켜줍니다.

[1번째 자리] 스택에 4를 push 합니다. (stack : 4)

[2번째 자리] 1은 4보다 크지 않으므로 스택에 psuh 합니다. (stack : 41)

[3번째 자리] 7은 1보다 크므로 스택을 pop 해줍니다. 꺼낸 횟수가 1 증가합니다. (stack : 4, cnt = 1)

7은 4보다 크므로 스택을 pop 해주고, 7을 push 합니다. 꺼낸 횟수가 1 증가합니다. (stack : 7, cnt = 2)

[4번째 자리] 7은 7보다 크지 않으므로 7을 push 합니다. (stack : 77)

[5번째 자리] 2는 7보다 크지 않으므로 2를 push 합니다. (stack : 772)

[6번째 자리] 5는 2보다 크므로 스택을 pop 해주고, 꺼낸 횟수를 1 증가시켜줍니다. (stack : 77, cnt = 3)

5는 7보다 크지 않으므로 5를 psuh 합니다. (stack : 775, cnt = 3)

[7번째 자리] 2는 5보다 크지 않으므로 2를 push 합니다. (stack : 7752)

[8번째 자리] 8은 2보다 크므로 스택을 pop 해주고, 꺼낸 횟수를 1 증가시켜줍니다. (stack : 775, cnt = 4)

cnt 횟수가 K와 같아졌으므로 더 이상 꺼낼 수 없습니다. 남은 자리를 stack에 계속 push 합니다.

(stack : 775841, cnt = 4)

한편,

3 1

3 2 1

와 같은 경우는 한 번도 pop이 발생하지 않습니다. (cnt = 0)

따라서 위 과정을 거친 뒤 cnt가 K와 같아질 때까지 끝자리부터 pop 해줘야 합니다.

소스 코드

#include<iostream>
#include<stack>
#include<string>
using namespace std;
 
int N, K;
int cnt;
 
int main()
{
    string s;
    cin >> N >> K;
    cin >> s;
    stack<char> st;
    stack<char> st2;
    for (int i = 0; i < s.size(); i++)
    {
        while (!st.empty() && cnt < K && s[i] > st.top())
        {
            cnt++;
            st.pop();
        }
        st.push(s[i]);
    }
    while (cnt < K)
    {
        cnt++;
        st.pop();
    }
    //스택 순서 거꾸로 바꿔준 후 출력
    while (!st.empty())
    {
        st2.push(st.top());
        st.pop();
    }
    while (!st2.empty())
    {
        cout << st2.top();
        st2.pop();
    }
    return 0;
}