크게 만들기 C++ - 백준 2812

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

그리디 문제.

문제 접근

첫번째 방법 TLE

크게 만들기 위해서는 가장 앞에 자리수부터 큰 수를 배정해야한다.

이를 구현하기 위해 우선순위 큐에 pair<계수, 인덱스>(불가능한 경우를 탐색하기 위해 인덱스로 체크함)

로 구현했는데 큐에 넣다 뺐다하는 과정이 있어서 자명히도 TLE가 났다.

따라서 다른 방식을 찾아야했다.

#include <bits/stdc++.h>
using namespace std;

int n,k;
char c;
string ans("");
int cnt=0,s=0;

struct compare{
    bool operator()(pair<int, int> &l, pair<int, int> &r){
        if(l.first==r.first) return l.second>r.second;
        return l.first<r.first;
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> c;
        pq.push({c-'0',i});
    }
    while(cnt<n-k){
        pair<int, int> now=pq.top();
        pq.pop();
        if(now.second<s) continue;
        if(n-now.second-1>=n-k-cnt-1){
            ans+=now.first+'0';
            cnt++;
            s=now.second;
        }
        else{
            stack<pair<int, int>> st; st.push(now);
            while(true){
                now=pq.top(); pq.pop(); st.push(now);
                if(n-now.second-1>=n-k-cnt-1){
                    ans+=now.first+'0';
                    cnt++;
                    s=now.second;
                    while(!st.empty()){
                        if(st.top().second>s) pq.push(st.top());
                        st.pop();
                    }
                    break;
                }
            }
            
        }
    }
    cout << ans;
    return 0;
}

(N의 범위가 5e5이므로 $O(N)$이거나 $O(NlogN)$을 찾아야한다.)

다른 방법

맨 앞부터 탐색하면서 만약 현재 인덱스 $i$가 여태까지 배열한 계수보다 크다면

더 큰 수를 만들 수 있는 것이기에 인덱스 $i$에 있는 계수보다 작은 계수들을 다 지워준다.

앞, 뒤에 있는 계수를 제어해야 하기 때문에 deque를 써주어야한다.

(위와 같이 코드를 짰을 때 반례가 있었다. 다 지우지 않았는데 deque에 넣는 경우이다.)

다 지우지 않았을 때 뒤부터 지우는 부분을 추가해야 한다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string ans("");
int n,k,cnt=0;
char c;
deque<int> dq;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> c;
        while(!dq.empty() && c-'0'>dq.back() && cnt<k){
            dq.pop_back(); cnt++;
        }
        dq.push_back(c-'0');      
    }
    while(cnt<k){dq.pop_back();cnt++;}
    while(!dq.empty()){cout << dq.front();dq.pop_front();}
    return 0;
}