Codeforces #1492B Card Deck

문제

https://codeforces.com/problemset/problem/1492/B

걸린 시간

01 : 20 : 21

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> p(n);
        set<int> s;
        for(int i = 0; i < n; i++){
            cin >> p[i];
            s.insert(p[i]);
        }
        vector<int> ans;
        while(!p.empty()){
            vector<int> pp;
            int maxi = *s.rbegin();
            while(!p.empty()){
                int element = p.back();
                p.pop_back();
                s.erase(s.find(element));
                pp.push_back(element);
                if(element == maxi) break;
            }
            for(int i = pp.size()-1; i >= 0; i--)
                ans.push_back(pp[i]);
        }
        for(int i : ans) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

1부터 n까지의 숫자 카드로 구성된 배열 p 가 주어진다. 인덱스 순서대로 카드가 아래서부터 위로 쌓여 있는 형태라고 생각하면 된다. 문제는 카드를 위에서부터 k > 0 장씩 뽑아 Σ(1 <= i <= n) n^n-i * p[i] 값이 최대가 되도록 하는 덱의 구성을 물어본다.

n 의 제곱 수 이기 때문에 아래쪽 카드의 숫자가 높을수록 최대값에 가깝다. 수학적으로 증명을 할 순 없지만 극단적인 예로 {4, 3, 2, 1, 5} 와 {5, 1, 2, 3, 4} 를 비교해보면 후자가 더 크다는 것을 확인할 수 있다.

따라서 배열 p 에서 가장 큰 값이 나올 때까지 반복해서 카드를 뽑아 만든 새로운 덱이 정답이다. 하지만 최대값을 구할 때 O(n) 시간이 소요되면 전체 시간 복잡도는 O(n²) 으로 시간초과가 난다. 이를 해결하려면 숫자 카드가 1부터 n까지 중복되지 않는 수들로 구성되어 있다는 점을 이용해 배열 p 의 값을 정렬된 자료구조인 set 에 복사하여 관리하는 방법이 있다. 카드를 뽑을 때마다 해당 원소를 제거해가며 *s.rbegin() 함수로 최대값을 찾으면 O(nlogn) 복잡도가 되어 ac 를 받을 수 있다.