[JAVA] 부분집합 알아보기 알고리즘

부분집합 구하기 알고리즘은 처음 생각보다 어렵게 끝났던 문제였던거 같다.

boolen으로 선언된 allContained(long[] a1, long[] a2) 이란 함수에서 a1이 a2에 부분집합인가를 판별하면 된다.

모두 알겠지만 모든 공집합은 모든 집합의 부분집합이다. (이 간단한 개념이 뒤에서 날 혼란스럽게 했다.)

주어진 문제를 본다면

public static boolean allContained (long[] a1, long[] a2),

which checks whether each value that occurs in array a1 is also contained in array

a2. A value can occur more than once in an array. The contents of array a1 and a2

should not be changed.

The method should be as efficient as possible and should deliver results quickly

even for very long arrays (e. g. 1 million elements).

그리고 주어진 템플릿은 이렇다.

package assignment1;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Set;

public class Exercise_1_4_Containment {

/**  

* Checks if every value contained in a1 is also contained in a2 */

public static boolean allContained(long[] a1, long[] a2) {

//TODO

//TODO

//TODO

//TODO

//TODO

return false; //TODO

}

public static final int MAX_LEN = 1000000;

public static void main(String[] args) {

long[] m0 = {};

long[] m1 = { 1, 2, 5 };

long[] m2 = { 4, 3, 2, 1, 8, 7, 6, 5 };

long[] m3 = { 2, 1, 5 };

long[] m4 = { 2, 1, 4, 3, 2 };

System.out.println("m0 subset of m1: result " + allContained(m0, m1) + " | expected: true");

System.out.println("m0 subset of m2: result " + allContained(m0, m2) + " | expected: true");

System.out.println("m0 subset of m3: result " + allContained(m0, m3) + " | expected: true");

System.out.println("m0 subset of m4: result " + allContained(m0, m4) + " | expected: true");

System.out.println("m1 subset of m0: result " + allContained(m1, m0) + " | expected: false");

System.out.println("m1 subset of m2: result " + allContained(m1, m2) + " | expected: true");

System.out.println("m2 subset of m1: result " + allContained(m2, m1) + " | expected: false");

System.out.println("m0 subset of m0: result " + allContained(m0, m0) + " | expected: true");

System.out.println("m1 subset of m1: result " + allContained(m1, m1) + " | expected: true");

System.out.println("m1 subset of m3: result " + allContained(m1, m3) + " | expected: true");

System.out.println("m3 subset of m1: result " + allContained(m3, m1) + " | expected: true");

System.out.println("m4 subset of m0: result " + allContained(m4, m0) + " | expected: false");

System.out.println("m4 subset of m1: result " + allContained(m4, m1) + " | expected: false");

System.out.println("m4 subset of m2: result " + allContained(m4, m2) + " | expected: true");

System.out.println("m4 subset of m3: result " + allContained(m4, m3) + " | expected: false");

System.out.println("m4 subset of m4: result " + allContained(m4, m4) + " | expected: true");

// Running time test:

for (int len = 100; len <= MAX_LEN; len *= 10) {

System.out.println("Array length " + len + ": ");

long[] a1 = new long[len];

long[] a2 = new long[len];

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

a1[i] = i;

a2[len - 1 - i] = i;

}

long start = System.nanoTime();

boolean result = allContained(a1, a2);

long ende = System.nanoTime();

System.out.println("\ta1 contained in a2: " + result + " Running time: "

+ ((ende - start) / 1e6) + " ms");

}

}

}

문제를 보면 The contents of array a1 and a2 should not be changed 라고 명시가 되어있다.

이걸 해석하는데 있어서 문제가 생겼는데 

첫번째로는 배열의 혹은 집합의 원소들의 값을 변경하지 말라는건지

두번째로는 배열의 순서를 변경하지 말라는건지 의문이었지만

만약 순서를 변경하지 않고 프로그래밍을 하게 되면 런타임을 측정할 때 엄청난 값이 나왔다... 따라서 import되어있던 hashset을 사용하기로 하였다.

public static boolean allContained(long[] a1, long[] a2) {

int lengtha2 = a2.length;

int lengtha1 = a1.length;

int search = 0;

HashSet<Long> hset= new HashSet<>(); 

        

        // hset stores all the values of arr1 

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

        { 

            if(!hset.contains(a2[i])) 

                hset.add(a2[i]); 

        } 

              

        // loop to check if all elements of arr2 also 

        // lies in arr1 

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

        { 

            if(!hset.contains(a1[i])) 

                return false; 

        } 

        return true; 

         //HASH SET

/*

if (lengtha1 > lengtha2)

return false;

else if (lengtha1 == 0)

return true;

else

for (int k=0; k<lengtha1; k++)

{

for (int j=0 ; j<lengtha2 ; j++)

{

if (a1[k] != a2[j])

{

search++;

continue;

}

else

{

search=0;

break;

}

}

}

if (search == a1.length)

return false;

return true;

*/ //sorting

}

처음에 생각한 방식은 a1에 있는 값이 a2에 없다면 그것은 자연스럽게 부분집합이 아닌걸 증명하기 때문에 만약 하나라도 값이 없다면 자동으로 false를 리턴하는 방식으로 코드를 짰다. (이땐 hashset을 공부하지 않아 그 사용법을 몰랐다.)

하지만 배열의 길이가 엄청나게 길어질때 그 효율성이 너무나 떨어져서 포기하고 말았다... 

그러던중 템플릿에 hashset이 import된 것을 보고 hashset을 사용한 것 이 다.

보면 주석처리한 위의 방식은 hashset을 사용 한 방식 이다. a1과 a2를 각각 해쉬테이블에 집어넣어 비교하는 방식이다.

이번 문제는 hashset을 알았다면 쉽게 넘어갔나 하는 생각이다.