[BOJ 백준] 2812번 크게 만들기

문제

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

2812번: 크게 만들기

접근

처음에는 쉬운 문제인 줄 알았으나 생각보다 신경 써 줘야 하는 게 많았던 문제 였다.

먼저 연속되는 수 중에서 앞의 수가 뒤의 수보다 작으면 지워준다. 제일 앞에 오는 수가 클수록 결론적으로 큰 수가 되기 때문이다.

이때 k개만큼 지우지 못했는데 앞의 수가 뒤의 수보다 작은 것이 없는 경우가 있다. (ex 87654) 이럴 때는 뒤에서부터 필요한 만큼 추가로 지워줘야 한다.

 

아래는 내가 예외를 찾을 때 썼던 테스트케이스이다.

6 2
987654
// ans : 9876

13 5
1980766254321
// ans : 98766543

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, k;
vector<char> start;
queue<char> back;

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        char temp;
        cin >> temp;
        back.push(temp);
    }
    start.push_back(back.front());
    back.pop();
    while (k != 0) {
        if (back.empty())
            break;
        if (start.back() < back.front()) {
            start.pop_back();
            k--;
        }
        if (start.size() == 0 || start.back() >= back.front()) {
            start.push_back(back.front());
            back.pop();
        }
    }
    for (int i = k; i > 0; i--) {
        start.pop_back();
    }
    string ans = "";
    for (int i = 0; i < start.size(); i++) {
        ans.push_back(start[i]);
    }
    while (!back.empty()) {
        ans.push_back(back.front());
        back.pop();
    }
    cout << ans;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study