식사 계획 세우기

백준 25406번: 식사 계획 세우기

아이디어

이전에 먹지 않은 음식 중에서 가장 인덱스가 앞에 있는 음식을 먹는다. 이 때 한 종류의 음식이 과반수를 넘어가면 그 음식 먼저 먹는다.

과반수를 넘는지 확인하기 위해 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 쓰려니까 헷갈렸다.