[BOJ/백준][Gold5] 2812 : 크게 만들기 (C++)

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

2812번: 크게 만들기

 

 

[난이도] Gold5
[유형] 우선순위큐

[풀이]
N자리에서 K자리를 지워야 하므로
N-K 자리의 수를 만들어야 한다.
가장 큰 자리수에 큰 수가 올수록 유리하다.
큰 자리수의 숫자부터 b[0]~b[N-1]에 저장하기로 하면
b[0]은 a[0]~a[N-K] 중에 가장 큰수,
b[1]은 (b[0]의 a에서의 index)~a[N-K+1] 중에 가장 큰수,
b[2]은 (b[1]의 a에서의 index)~a[N-K+2] 중에 가장 큰수
....
으로 구할 수 있다.
그런데 for문으로 큰 수들을 구하면 시간초과가 나므로 우선순위 큐를 이용하였다.

a 배열에서 0~N-K-1 까지의 수를 pq에 {a[i],i} pair로 index까지 같이 넣어놓고
K번의 반복동안
N-K+i번 pair를 추가하면서 pq에서 최댓값을 찾으면 NlogN의 시간으로 답을 찾을 수 있다.

 

 

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N,a[500000],K;

struct cmp{
    bool operator()(pair<int,int> a,pair<int,int> b){
        if(a.first<b.first) return 1;
        else if(a.first==b.first) return a.second > b.second;
        return 0;
    }
};
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%1d",&a[i]);
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
    K=N-K;
    for(int i=0;i<N-K;i++) pq.push({a[i],i});
    int s=-1,e;
    for(int i=0;i<K;i++){
        e=N-K+i;
        pq.push({a[e],e});
        while(!pq.empty()){
            auto qt = pq.top(); pq.pop();
            if(qt.second>s) {
                s=qt.second;
                break;
            }
        }
        printf("%d",a[s]);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2812.cpp