백준 2812: 크게 만들기

문제 요약

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

문제 분류

• 자료 구조
• 그리디 알고리즘
• 스택

문제 풀이

앞 자리의 수를 뒷 자리 수보다 반드시 크게 만드는 그리디 알고리즘문제이다. 입력은 string으로 받아주어서 각 문자로 처리하였다.

결국 이 문제를 관통하는 조건은, '앞 자리의 수가 뒷 자리 수보다 클 것'이다. 현재 인덱스를 i라고 하면, i번째의 숫자는 0~i - 1의 인덱스의 수보다 작아야 한다. 크다면 최대 k개를 지워서 앞자리로 옮겨야 한다. 이는 스택으로 구현할 수 있다.

입력 받은 문자열을 0번 부터 스택에 push()한다. 이때, 스택의 top()보다 현재 인덱스의 값(s[i])이 더 크다면 pop()연산으로 빼 준 후 그 다음의 top()과 비교한다. 즉, 스택은 내림차순으로 쌓아져야 하며, 위배될 경우 pop()을 해주어야 한다.

k를 전부 사용할 경우 무조건 push()를 해주고, 이미 내림차순으로 주어지는 등 k를 전부 사용하지 않은 경우에도 마지막에는 스택의 top()부터 그 개수만큼 pop()해주었다.

마지막으로 pop()을 해주면서 출력 문자열 res에 붙혀주고, 스택이라 역순이므로 마지막에 뒤집어주는 연산을 하였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
    int n, k, i;
    string s, res = "";
    stack<char> st;
    cin >> n >> k >> s;
    for (i = 0; i < n;) {
        if (st.empty() || st.top() >= s[i] || k <= 0) {
            st.push(s[i]);
            i++;
        }
        else {
            k--;
            st.pop();
        }
    }
    while (k-- > 0 && !st.empty())
        st.pop();
    while (!st.empty()) {
        res += st.top();
        st.pop();
    }
    reverse(res.begin(), res.end());
    cout << res;
    return 0;
}