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

2812번: 크게 만들기

그리디를 이용한 문제이다. 먼저 N자리의 숫자를 문자열로 입력을 받고 또 다른 문자열 result에 입력받은 문자열의 맨 앞숫자를 저장해준다. 이 후 반복문을 돌면서 result의 가장 뒷숫자와 비교하며 작은 숫자는 reulst.pop_back을 해주고 현재 숫자를 넣어주면서 빼준 만큼 카운트를 해주었다. 이때 남은 숫자 개수와 남은 카운트 수가 같다면 result 뒷숫자보다 현재 숫자가 클 경우에만 반복문을 돌려주었다. 생각보다 쉽게 풀 수 있었던 문제였다.

#include <iostream>

using namespace std;

int N, K;
string s, result = "";

void solution() {
    int count = K;

    result.push_back(s[0]);

    for (int i = 1; i < N; i++) {
        if (N - i == count && result.back() >= s[i]) {
            count--;
            continue;
        }

        while (!result.empty() && result.back() < s[i]) {
            if (count == 0) break;

            result.pop_back();
            count--;
        }

        result.push_back(s[i]);
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    cin >> s;

    solution();

    return 0;
}