Lottery

Code

import java.util.Arrays;

import java.util.Comparator;

public class Lottery

{

    long perm(long a, long b) {

        long num = 1;

        for (int i = 0; i < b; i++)

            num *= a--;

        return num;

    }

    long fact(long a) {

        long num = 1;

        for (int i = 2; i <= a; i++)

            num *= i;

        return num;

    }

    long cbn(long n, long r) {

        if(r > n/2) r = n-r;

        long denom=1, numer=1;

        while(r > 0) {denom *= n--; numer *= r--;}

        return denom / numer;

    }

    long calOutcomes(long choices, long blanks, boolean sorted, boolean unique) {

        long outcomes = 1;

        if (sorted && unique)

            outcomes = cbn(choices, blanks);

        else if (sorted && !unique)

            outcomes = cbn(choices+blanks-1, blanks);

        else if (!sorted && unique)

            outcomes = perm(choices,blanks);

        else if (!sorted && !unique)

            outcomes = (long)Math.pow(choices,blanks);

        return outcomes;

    }

    public String[] sortByOdds(String[] rules) {

        int n = rules.length;

        Arrays.sort(rules, new Comparator<String>() {

            public int compare(String A, String B) {

                String[] spA = A.split(":")[1].split(" ");

                int choicesA = Integer.parseInt(spA[1]);

                int blanksA = Integer.parseInt(spA[2]);

                String[] spB = B.split(":")[1].split(" ");

                int choicesB = Integer.parseInt(spB[1]);

                int blanksB = Integer.parseInt(spB[2]);

                long outcomesA = calOutcomes(choicesA, blanksA, spA[3].charAt(0)=='T', spA[4].charAt(0)=='T');

                long outcomesB = calOutcomes(choicesB, blanksB, spB[3].charAt(0)=='T', spB[4].charAt(0)=='T');

                if (outcomesA < outcomesB)

                    return -1;

                else if (outcomesA > outcomesB)

                    return 1;

                else

                    return A.compareTo(B);

            }

        });

        String[] name = new String[n];

        for (int i = 0; i < n; i++)

            name[i] = rules[i].split(":")[0];

        return name;

    }

}

Problem

최대 숫자와 숫자를 적는 빈 칸이 각기 다른 로또 복권이 주어진다. 각각의 로또에 대한 확률을 구하고, 당첨 확률이 가장 큰 로또 순으로 정렬한 String 배열을 반환해야 한다. 확률이 같을 경우, 문자열을 비교하여 알파벳 순으로 정렬한다.

Explanation

sorted와 unique의 논리값에 따라 계산을 수행한다.

1. sorted && unique
   한 번 나온 숫자들의 집합은 다시 나올 수 없으므로 조합을 이용한다.
2. sorted && !unique
   1번과 마찬가지로 조합을 이용한다. 다른 점은 숫자의 중복을 허용한다는 점이다. 중복 숫자를 포함한 조합은 선택 가능한 숫자의 개수가 choices+blanks-1인 조합과 같다. (직접 숫자를 넣어서 비교해 보았다.)
3. !sorted && unique
   조합과 달리 이미 나온 숫자들의 집합이 순서만 다르게 해서 다시 나올 수 있다. 즉, 순열과 같다.
4. !sorted && !unique
   각 칸마다 모든 숫자를 적을 수 있으므로 결과는 choicesblanks이다.

References

https://community.topcoder.com/stat?c=problem_solution&cr=277659&rd=4515&pm=1659