[Moderate] interview questions #21

[rygh4775]

[tgi01054]

문제 설명

{4, 1, 2, 1, 1, 2} 의 합 11
{3, 6, 3, 3} 의 합 13

집합 A에서 1을 집합 B의 3를 교환
{4, 3, 2, 1, 1, 2} 의 합 13
{1, 6, 3, 3} 의 합 13
하면 sum swap 이 이루어 집니다.

Naive version

    public static int sum(int[] array) {
        int s = 0;
        for (int a : array) {
            s += a;
        }
        return s;
    }

    public static int[] findSwapValues(int[] array1, int[] array2) {
        int sum1 = sum(array1);
        int sum2 = sum(array2);

        for (int one : array1) {
            for (int two : array2) {
                int newSum1 = sum1 - one + two;
                int newSum2 = sum2 - two + one;
                if (newSum1 == newSum2) {
                    int[] values = {one, two};
                    return values;
                }
            }
        }

        return null;
    }

시간 복잡도: O(AB)

Better version

sumA - a + b = sumB - b + a
2a - 2b = sumA - sumB
a - b = (sumA - sumB) / 2

a,b 는 정수이므로 a - b 는 짝수이다.

target = a - b = (sumA - sumB) / 2 
으로 해서 코딩하면 

    public static int[] findSwapValues(int[] array1, int[] array2) {
        Integer target = getTarget(array1, array2);
        if (target == null) return null;

        for (int one : array1) {
            for (int two : array2) {
                if (one - two == target) {
                    int[] values = {one, two};
                    return values;
                }
            }
        }

        return null;
    }

    public static Integer getTarget(int[] array1, int[] array2) {
        int sum1 = sum(array1);
        int sum2 = sum(array2);

        if ((sum1 - sum2) % 2 != 0) return null;

        return (sum1 - sum2) / 2;
    }   

    public static int sum(int[] array) {
        int s = 0;
        for (int a : array) {
            s += a;
        }
        return s;
    }

시간 복잡도: O(AB)

More better version

target = a - b = (sumA - sumB) / 2 
에서 
b = target - a 
이므로

집합 B를 hash table 에 loading 후 lookup 하면 개선할 수 있다.

    public static int[] findSwapValues(int[] array1, int[] array2) {
        Integer target = getTarget(array1, array2);
        if (target == null) return null;
        return findDifference(array1, array2, target);
    }

    public static int[] findDifference(int[] array1, int[] array2, int target) {
        HashSet<Integer> contents2 = getContents(array2);
        for (int one : array1) {
            int two = one - target;
            if (contents2.contains(two)) {
                int[] values = {one, two};
                return values;
            }
        }

        return null;
    }

    public static Integer getTarget(int[] array1, int[] array2) {
        int sum1 = sum(array1);
        int sum2 = sum(array2);

        if ((sum1 - sum2) % 2 != 0) return null;
        return (sum1 - sum2) / 2;
    }

    public static HashSet<Integer> getContents(int[] array) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int a : array) {
            set.add(a);
        }
        return set;
    }

    public static int sum(int[] array) {
        int s = 0;
        for (int a : array) {
            s += a;
        }
        return s;
    }

시간 복잡도: O(A+B)

• 해쉬 테이블 로딩 O(B)
• 집합 iterate O(A)

More more better version

2개의 집합을 ASC sort 하면 개선 할 수 있습니다.

    public static int[] findSwapValues(int[] array1, int[] array2) {
        Integer target = getTarget(array1, array2);
        if (target == null) return null;
        return findDifference(array1, array2, target);
    }

    public static int[] findDifference(int[] array1, int[] array2, int target) {
        Arrays.sort(array1);
        Arrays.sort(array2);

        int a = 0;
        int b = 0;

        while (a < array1.length && b < array2.length) {
            int difference = array1[a] - array2[b]; 
            /* Compare difference to target. If difference is too small, then
             * make it bigger by moving a to a bigger value. If it is too big,
             * then make it smaller by moving b to a bigger value. If it's
             * just right, return this pair. */
            if (difference == target) {
                int[] values = {array1[a], array2[b]};
                return values;
            } else if (difference < target) { 
                a++;
            } else {
                b++;
            }
        }

        return null;
    }

시간 복잡도: O(AlogA + BlogB) = O(AlogA + BlogB) + O(A+B)

• 정렬 비용: O(AlogA + BlogB)
• swap 계산 비용: O(A+B)