Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-28

Sets

| 18:25

問題文

集合演算。

class Sets {
public:
    vector <int> operate(vector <int> A, vector <int> B, string operation) {
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        if (operation == "UNION") {
            return union_set(A, B);
        } else if (operation == "INTERSECTION") {
            return intersection(A, B);
        } else if (operation == "SYMMETRIC DIFFERENCE") {
            return symmetric_difference(A, B);
        } else {
            return vector<int>();
        }
    }
private:
    vector<int> union_set(const vector<int>& A, const vector<int>& B) {
        set<int> tmp_union;
        for (int i = 0; i < A.size(); i++) tmp_union.insert(A[i]);
        for (int i = 0; i < B.size(); i++) tmp_union.insert(B[i]);
        vector<int> ret;
        for (set<int>::const_iterator itr = tmp_union.begin();
                itr != tmp_union.end(); itr++)
            ret.push_back(*itr);
        return ret;            
    }
    vector<int> intersection(const vector<int>& A, const vector<int>& B) {
        int i=0, j=0;
        vector<int> ret;
        while (i<A.size() && j<B.size()) {
            if (A[i] == B[j]) {
                ret.push_back(A[i]);
                i++; j++;
            } else if (A[i] < B[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ret;
    }
    vector<int> symmetric_difference(const vector<int>& A, const vector<int>& B) {
        vector<int> uni = union_set(A, B);
        vector<int> inter = intersection(A, B);
        vector<int> ret;
        for (int i = 0; i < uni.size(); i++) {
            if (find(inter.begin(),inter.end(),uni[i]) == inter.end())
                ret.push_back(uni[i]);
        }
        return ret;
    }
};