이전에 먹지 않은 음식 중에서 가장 인덱스가 앞에 있는 음식을 먹는다. 이 때 한 종류의 음식이 과반수를 넘어가면 그 음식 먼저 먹는다.
과반수를 넘는지 확인하기 위해 set 하나, 이전에 먹지 않은 음식 중 가장 인덱스가 앞에 있는 음식을 확인하기 위해 set 하나, 각 음식별로 가장 인덱스가 앞에 있는 음식을 찾기 위해 pq N개가 필요하다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> v(n);
vector<priority_queue<int, vector<int>, greater<int>>> vpq(n+1); // vpq[num]: idx pq
set<pair<int, int>> cset; // count, num
set<pair<int, int>> iset; // idx, num
for (int i = 0; i < n; i++) {
cin >> v[i];
vpq[v[i]].push(i+1);
if (vpq[v[i]].size() > ceil(n/2.0)) {
cout << -1 << '\n';
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (!vpq[i].empty()) {
cset.insert({vpq[i].size(), i});
iset.insert({vpq[i].top(), i});
}
}
int last = -1;
int curn = n;
while (curn--) {
auto maxelem = cset.rbegin();
if ((*maxelem).first > ceil(curn/2.0)) {
// use maxelem
auto [cnt, num] = *maxelem;
int idx = vpq[num].top();
last = num;
cout << vpq[num].top() << ' ';
vpq[num].pop();
iset.erase({idx, num});
cset.erase({cnt, num});
if (cnt-1) {
cset.insert({cnt-1, num});
iset.insert({vpq[num].top(), num});
}
}
else {
// use minidx
auto minidxelem = iset.begin();
while ((*minidxelem).second == last && minidxelem != iset.end()) minidxelem++;
auto [idx, num] = *minidxelem;
int cnt = vpq[num].size();
last = num;
cout << idx << ' ';
vpq[num].pop();
iset.erase({idx, num});
cset.erase({cnt, num});
if (cnt-1) {
cset.insert({cnt-1, num});
iset.insert({vpq[num].top(), num});
}
}
}
return 0;
}
맨날 pq만 쓰다가 set 쓰려니까 헷갈렸다.