Distant Barcodes

1054. Distant Barcodes

class Solution {
    struct cmp{
        bool operator()(int a, int b){
            return (a & 0xffff) < (b & 0xffff);
        }
    };

public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        if (barcodes.size() < 3) {
            return barcodes;
        }

        map<int, int> mp;
        for (auto b: barcodes) {
            mp[b]++;
        }
        priority_queue<int, vector<int>, cmp> pq;

        vector<int> bc, result;
        for (auto [k, v]: mp) {
            pq.push(k << 16 | v);
        }

        int a = pq.top();
        pq.pop();
        while (!pq.empty()) {
            result.push_back(a>>16);
            int n = --a;
            a = pq.top();
            pq.pop();
            if (n & 0xffff) {
                pq.push(n);
            }
        }
        if (a & 0xffff) {
            result.push_back(a >> 16);
        }
        return result;
    }
};

바코드 종류별 개수 max heap 기준으로 우선순위 큐 에 넣는다.
큐에서 하나 꺼내서(a) 해당 바코드 종류를 결과에 넣는다.
큐에서 하나 꺼내 놓는다.(b)
a 의 개수가 남아있으면 다시 큐에 넣고 다시 b 종류를 결과에 넣는다.
큐가 빌때까지 반복한다.

barcodes.size() == n

Time: O(n·log(n))

Space: O(n)