[Greedy / Gold 5] 2812번: 크게 만들기

문제 출처

www.acmicpc.net/problem/2812

문제 내용

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

풀이

K와 N의 크기가 예사롭지 않은 걸 보면 시간복잡도가 O(N+K) 정도 이하여야 한다는 걸 알 수 있다. 그리디 알고리즘을 이용한다는 전제하에  어떤 조건으로 풀어낼 수 있을지 고민했다.

  숫자를 하나씩 지워나갈 때마다 항상 가장 큰 수를 만들어나가면 K개를 지워도 가장 큰 수를 알아낼 수 있다는 것은 자명하다. 

  숫자의 크기를 결정하는 것은 왼쪽편(자릿수가 큰 쪽)이다.

이러한 사실을 중점으로 생각해보면 왼쪽부터 오른쪽으로 진행하면서 숫자들을 점검하는데, 이 때 오른편의 수가 나보다 큰 수를 찾아서 없애야 한다. 즉, 숫자가 2156007에서 하나를 지우면 256007이다. 이렇게 하면 숫자를 하나씩 지울 때마다 최대한 큰 수가 왼쪽으로 오도록 유도할 수 있기 때문이다.

 

  * 구현할 때 vector를 쓰면 erase의 시간복잡도가 O(N)이므로 list STL을 쓰도록 한다.

코드

#include <iostream>
#include <list>
using namespace std;

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

    int N, K; cin >> N >> K;
    string str; cin >> str;
    
    list<int> num;
    for (int i = 0; i < N; ++ i) {
        num.push_back((int)str[i] - 48);
    }
    
    list<int>::iterator it = num.begin();
    list<int>::iterator it_prev = num.begin();
    
    // 오른쪽 수가 나보다 큰 수 중에서 가장 왼쪽인 수의 배열을 찾는다.
    while (it != num.end()) {
        if (*it < *(next(it, 1))) {
            if (it == num.begin()) {
                it_prev = it;
                it = next(it, 1);
                num.erase(it_prev);
            } else {
                it_prev = it;
                it = prev(it, 1);
                num.erase(it_prev);
            }
            
            if (--K == 0) break;
        } else
            it = next(it, 1);
    }
    
    // 아직 뺴야할 숫자가 남아있다면 뒤에서부터 뺴버린다.
    it = num.end();
    if (K > 0) {
        while (K > 0) {
            num.erase(it);
            
            -- K;
        }
    }
        
    for (it = num.begin(); it != num.end(); ++ it)
        cout << *it;
    
    cout << endl;
        
    return 0;
}