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

https://www.acmicpc.net/problem/2812

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    string num;
    vector<char> ans;

    cin >> n >> k;

    cin >> num;


    int cnt = 0;

    stack<char> s;


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

    while (cnt < k) {
        cnt++;
        s.pop();
    }

    while (!s.empty()) {
        ans.push_back(s.top());
        s.pop();
    }

    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }

    return 0;
}

1. 문제

50만자리 이하 n 자리 숫자가 주어진다. 여기서 k개의 수를 지워 새 숫자를 만들려 할 때, 해당 숫자의 최댓값을 구하라.

2. 풀이

핵심은 다음 자리 숫자가 현재 자리 숫자보다 크다면 현재 자리 숫자를 제거하는 것이다. 

    stack<char> s;


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

각 숫자를 스택에 넣는데, 현재 숫자보다 다음에 들어올 숫자가 더 크다면 현재 숫자를 pop한다. k 개의 숫자를 제거하는 문제이므로 이도 확인해준다. 그 후 해당 숫자를 push한다.

    while (cnt < k) {
        cnt++;
        s.pop();
    }

연산이 끝나고도 k 만큼 지워지지 않았다면 스택에서 pop한다. 스택의 top은 마지막자리 숫자이고, 위 연산에 의해 가장 작은 숫자가 들어가 있으므로 top에서 pop을 하여 답을 구할 수 있다.

    while (!s.empty()) {
        ans.push_back(s.top());
        s.pop();
    }

    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }

숫자를 스택에 넣었으므로 pop하여 저장하고, 거꾸로 출력해주면 정답을 구할 수 있다.