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

www.acmicpc.net/problem/2812

2812번: 크게 만들기

풀이

스택을 이용해 풀 수 있는 문제입니다.

 

219879가 입력되었고, 지워야 할 숫자가 3개라고 생각해봅시다. 

 

먼저 첫 번째 자릿수인 2를 스택에 push 합니다.

 

이후부터 각 자릿수를 탐색하며 스택에 push 되어있는 숫자를 비교합니다.

 

만약 탐색 중인 자릿수의 숫자가 스택에 push 되어있는 숫자보다 크다면

 

스택의 숫자를 pop 해주며 k를 감소 시켜 줍니다.

 

즉 현재 지워야 할 숫자가 남아있고, 이전 자릿수들의 숫자가 현재 자릿수의 숫자보다 작다면 지워주는 것입니다.

 

219879의 경우 아래 표와 같이 진행됩니다.

 

2	1	9	8	7	9
push / 2
	push / 2, 1
pop / k = 2	pop / k = 1	1 < 9, 2 < 9
		push / 9
			push / 9, 8
				push / 9, 8, 7
				pop / k = 0	7 < 9
					push / 9, 8, 9

만약 위 경우에서 지워야 할 숫자 k가 4라면, 스택에 저장된 8이 pop 되어 스택에는 9, 9가 남을 것입니다.

 

k가 3이기에 7과 비교해 7까지만 pop하고 스택에는 9, 8, 9가 남아있게 되어 가장 큰 수는 989가 됩니다.

 

#include<iostream>
#include<vector>

using namespace std;

int main(void)
{
    int n, k; cin >> n >> k;
    string s; cin >> s;
    
    vector<char> v;

    for (int i = 0; i < n; i++) {
        while (k && !v.empty() && v.back() < s[i]) {
            v.pop_back();
            k--;
        }
        v.push_back(s[i]);
    }

    size_t sz = v.size();
    for (size_t i = 0; i < sz - k; i++) {
        cout << v[i];
    }

    return 0;
}

반례

Input

5 2

38125

Output

825

 

Input

10 4

3761185129

Output

785129