PostAddsense


SetComparison Topcoder



import java.util.HashSet;
import java.util.TreeSet;
import java.util.StringTokenizer;

public class SetComparison
{
    HashSet getSet(StringTokenizer st) {
        HashSet s = new HashSet<String>();
        String t = st.nextToken();
        while (!t.equals("}")) {
            if (t.equals("{")) s.add(getSet(st));
            else if (!t.equals(",")) s.add(t);
            t = st.nextToken();
        }

        return s;
    }
    
    public String[] relation(String _a, String _b) {
        StringTokenizer st = new StringTokenizer(_a,"{},",true);
        st.nextToken();
        HashSet a = getSet(st);
        st = new StringTokenizer(_b,"{},",true);
        st.nextToken();
        HashSet b = getSet(st);
        TreeSet<String> ret = new TreeSet<String>();

        if (b.contains(a)) ret.add("MEMBER");
        boolean eq = a.equals(b);
        if (eq) ret.add("EQUIVALENT");
        if (b.containsAll(a)) {
            ret.add("SUBSET");
            if (!eq) ret.add("PROPER SUBSET");
        }
        if (a.size() == 1<<b.size()) {
            boolean isPowerset = true;
            for (Object o : a)
                if (b.contains(o)) {isPowerset = false; break;}

            if (isPowerset) ret.add("POWERSET");
        }
        if (a.size() == b.size()) ret.add("EQUIPOTENT");

        return ret.toArray(new String[0]);
    }
}


Explanation

  • 객체 A에 타입을 명시하지 않은 객체 B를 저장하면, A의 타입에 상관없이 B의 모든 요소가 그대로 A에 저장된다. (주의:  B의 요소를 개별적으로 저장하지 않는다)
  • Powerset은 2a.size() = b.size() 공식을 가진다. 공식을 만족하면 a가 b의 성분을 가지고 있는지 확인한다. a에 b의 성분이 없으면 Powerset이므로 ret에 넣어준다.


References