문제

2812번: 크게 만들기

풀이

입력으로 주어진 숫자의 순서를 바꿀 수 없다.
k개의 숫자를 지운 수가 크기 위해서는 가능한 앞자리에 큰 수가 와야 한다.
따라서 앞의 수보다 뒤에 큰 수가 있다면 지울 수 있는 한 많이 지워 큰수가 앞에 위치할 수 있도록 해야 한다.

이를 위해 스택 자료구조를 사용한다.
입력으로 주어진 수의 첫자리 수 부터 스택에 넣는다.
스택에 넣기 전 스택의 마지막 수와 다음 입력으로 주어지는 수를 비교하여 스택의 수가 크다면 입력으로 주어진 수를 스택에 넣고, 스택의 수가 작다면 스택에서 꺼낸 후 다시 스택의 마지막 수를 비교하며 반복한다.
스택에서 제거된 수가 k가 될 때까지 반복하며 입력으로 주어진 모든 수에 대해 반복이 끝났다면
스택안의 수를 앞에서부터 n-k개 출력하면 된다.

문제도 간단하고 코드도 간단하지만 생각하기 너무 힘들었던 문제였다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n, k;
    string input;
    vector<char> stack;
    int cnt = 0;
    cin >> n >> k;
    cin >> input;
    
    for (int i=0; i<n; i++){
        while (!stack.empty() && input.at(i) > stack.back()){
            if (k==cnt) break;
            stack.pop_back();
            cnt++;
        }
        stack.push_back(input[i]);
    }

    for (int i=0; i < n-k; i++){
        cout << stack[i];
    }cout << endl;

    return 0;
}