WhichData

Code

import java.util.ArrayList;

import java.util.Arrays;

public class WhichData

{

    public int[] bestVariance(int[] sampleData, int varNum, int varDen) {

        Arrays.sort(sampleData);

        int sdLen = sampleData.length;

        double var = (double)varNum/varDen;

        double closest = 10001;

        int[] res = new int[0];

        for (int i = 1; i < Math.pow(2,sdLen); i++) {

            double sum = 0.0;

            double sumOfSquares = 0.0;

            ArrayList<Integer> ss = new ArrayList<Integer>();

            for (int j = i, k = 0; j > 0; j = j>>1,k++) {

                if ((j&1) == 1) {

                    sum += sampleData[k];

                    sumOfSquares += sampleData[k]*sampleData[k];

                    ss.add(sampleData[k]);

                }

            }

            double ssLen = ss.size();

            double svar = sumOfSquares/ssLen - (sum*sum)/(ssLen*ssLen);

            if (Math.abs(var-svar)==closest || Math.abs(Math.abs(var-svar)-closest)<=1e-9) {

                boolean flag = false;

                int len = (res.length < ss.size()) ? res.length : ss.size();

                for (int j = 0; j < len; j++) {

                    if (res[j] < ss.get(j)) break;

                    else if (res[j] > ss.get(j)) {flag = true; break;}

                }

                if (flag) {

                    res = new int[ss.size()];

                    for (int j = 0; j < ss.size(); j++)

                        res[j] = ss.get(j);

                }

            }

            else if (Math.abs(var-svar) < closest) {

                closest = Math.abs(var-svar);

                res = new int[ss.size()];

                for (int j = 0; j < ss.size(); j++)

                    res[j] = ss.get(j);

            }

        }

        return res;

    }

}

Explanation

• bit mask와 재귀를 사용하여 푸는 두 가지 방법이 있다. 재귀가 더 빠르지만 bit mask를 사용해 문제를 풀었다.
• 더블 자료형의 정밀도(1e-9)를 검사하는 if문을 먼저 넣어줘야 한다. 실제 계산에서는 똑같은 분산이지만, 컴퓨터 계산에서는 정밀도로 인해 뒤바뀔 수 있기 때문이다.
• 분산 계산 중 공통된 부분을 줄여서 계산했다. 참조한 사이트에 계산법이 나와 있다.

References

https://www.topcoder.com/tc?module=Static&d1=match_editorials&