[BOJ] 크게 만들기

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

BOJ - 크게 만들기

문제 유형: 모노토닉 스택, 스택, 그리디

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

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

 

입력

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

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

 

출력

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

 

풀이

두 가지 방법으로 풀었다:

1. 우선순위 큐를 이용한 풀이

N - K길이의 가장 큰 subsequence를 구하는 문제라고 볼 수도 있다.

우선순위 큐의 요소로는 <숫자, 인덱스>로 하고, 정렬 기준은 숫자에 대해서는 최대 힙, 인덱스에 대해서는 최소 힙으로 되게 한다.

우선, 앞 K개를 우선순위 큐에 넣는다. 0 ~ K-1인덱스의 요소들을 넣으면 된다. 마지막으로 요소를 이용한 인덱스를 추적하는 last변수에 -1을 넣는다.

 

그 이후, K번째 ~ N-1번째 요소에 대해서, 우선순위 큐에 이번 요소를 넣고, 우선순위 큐의 톱이 last보다 작은동안, 버린다. last이전의 것들은 사용할 수 없기 때문이다.

이제, 우선순위 큐의 톱에서 요소를 꺼내서 숫자를 정답에 append하고, 인덱스를 last에 저장한다.

 

최종적인 정답 문자열이 완성된다.

 

2. 모노토닉 스택을 이용한 풀이

스택의 밑바닥에는 최대한 큰 수가 오게 해야 한다.

그리고 최대 K개를 없앨 수 있다.

모노토닉 스택의 패턴대로, 스택의 톱이 이번에 넣을 요소보다 작다면, 다 꺼낸다. 이 작업은 최대 K번만 되도록 한다.

 

만약 K번이 되지 않았는데도 스택에 다 넣었다면, 그저 톱에서 나머지 개수만큼 pop하여 제거처리 한다.

이제, 스택에서 꺼내서 문자열을 구성하고, 스택이므로 뒤집어져있으므로, 다시 한번 뒤집어서 출력한다.

 

코드

C++

 

1 - 우선순위 큐를 이용한 풀이 (O(N log N))

#include <bits/stdc++.h>

using namespace std;

struct comp {
    bool operator()(const pair<char, int>& a, const pair<char, int>& b) {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    }
};

int main(int argc, char* argv[]) {
    int n, k;
    cin >> n >> k;
    string num;
    cin >> num;

    priority_queue<pair<char, int>, vector<pair<char, int>>, comp> pq;
    int last = -1;
    string ans = "";
    for (int i = 0; i < k; i++) {
        pq.emplace(num[i], i);
    }

    for (int i = k; i < n; i++) {
        pq.emplace(num[i], i);

        while (pq.top().second <= last) pq.pop();
        ans += pq.top().first;
        last = pq.top().second;
        pq.pop();
    }

    cout << ans << "\n";

    return 0;
}

 

2 - 모노토닉 스택을 이용한 풀이 (O(N))

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char* argv[]) {
    int n, k;
    cin >> n >> k;
    string num;
    cin >> num;

    stack<char> stk;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && stk.top() < num[i] && cnt < k) {
            stk.pop();
            cnt++;
        }

        stk.push(num[i]);
    }

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

    string ans = "";
    while (!stk.empty()) {
        ans += stk.top();
        stk.pop();
    }
    reverse(ans.begin(), ans.end());

    cout << ans << "\n";

    return 0;
}