두 배열을받아 부분집합 찾아내기

쉬운문제이지만 여러가지 알고리즘을 활용해 비교해 보았다.

 

문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

 

 

문제 입력 예시

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] base = new int[]{7, 1, 2, 3, 4, 5};
        int[] sample = new int[]{1, 3,7};

        boolean test = solution.isSubsetOf(base, sample);


        System.out.println(test);
    }
}

 

 

 

해결방법

스트림을 이용한 해결방법

class Solution {
    public boolean isSubsetOf(int[] base, int[] sample) {
        return IntStream.of(sample).allMatch((a)-> IntStream.of(base).anyMatch(b->a==b));
    }
}

스트림을 이용하여 가독성만을 높인 해결방법이다. 성능면에서는 좋은 해결방법이라 할수 없다.

 

 

반복문을 이용한 해결방법

class Solution {
    public boolean isSubsetOf(int[] base, int[] sample) {
         Arrays.sort(base);
         Arrays.sort(sample);
         
        if(base[base.length-1]<sample[sample.length-1]) return false;

        for(int samples:sample){
            for(int i =0; i<base.length; i++){
                if(samples==base[i]) break;
                if(samples<base[i]||i==base.length-1) return false;
            }
        }

        return true;
    }
}

반복문을 이용했으며 가독성은 좋지 않지만 성능을 조금더 개선 시킨 해결방법이다.

 

먼저 두 배열을 정렬해준뒤 sample의 마지막 인덱스의 값이 base의 마지막 인덱스의 값보다 클경우 부분집합이 이뤄질수 없으므로 바로 false를 리턴해준다.

 

반복문에서는 sample의 각 요소들을 base의 각 요소들과 비교해 주었으며 첫번째 조건문과 마찬가지로 비교되는 base의 인덱스의 값이 sample의 값 보다 클경우 부분집합이 이뤄질수 없다. 또한 base의 마지막 인덱스까지 접근했음에도 부분집합을 못찾을경우 false를 리턴.

 

 

Hash map을 이용한 해결방법

class Solution {
    public boolean isSubsetOf(int[] base, int[] sample) {
        HashMap<Integer,Boolean> hashMap = new HashMap<>();
        for(int bases:base) hashMap.put(bases,true);
        
        for(int samples:sample){
            boolean result = hashMap.containsKey(samples);
            if(result==false) return false;
        }
        return true;
    }
}

위의 두 방법의 경우 시간 복잡도는 O(nm)이지만 Hash map을 이용한 방법을 사용하여 O(n+m)으로 줄였다.

 

 

이진 탐색을 이용한 해결방법(번외)

class Solution {
    public boolean isSubsetOf(int[] base, int[] sample) {
        Arrays.sort(base);
        
        for(int samples:sample){
            boolean result = recursion(base,samples);
            if(result==false) return false;
        }

        return true;
    }

    boolean recursion(int[] base, int sample){
        if(base.length==1) {
            if(base[0]==sample) return true;
            else return false;
        }

        boolean result=true;
        int middle = base.length/2;

        if(base[middle] == sample) return true;
        else if(base[middle] > sample){
            int[] newArr = Arrays.copyOf(base, middle);
            result = recursion(newArr,sample);
        }
        else if(base[middle] < sample){
            int[] newArr = Arrays.copyOfRange(base, middle, base.length);
            result = recursion(newArr,sample);
        }
        return result;
    }
}

이진탐색을 이용한 방법이다.

 

이진탐색의 특성상 비교가 될 대상들의 배열은 정렬이 되있어야 하므로 제일먼저 base 배열을 정렬 시켜준뒤 sample배열의 모든 요소들을 비교를 해준다. (sample배열은 정렬할 필요 없음)

이후 재귀를 통해 해당 sample요소와 일치하는 값이 base배열에 존재하다면 true를 리턴해주고 없다면 base배열을 반으로 잘라 재귀를 돌려준다. 

 

위와 같이 이진 탐색을 활용하면 시간복잡도는 O(n log n)이 된다. 두개의 배열을 받아 비교해야하므로 이러한 시간복잡도를 가지게 된다.

 

하지만 만약 입력으로 들어온 배열 sample이 배열이 아닌 한개의 숫자이며 배열 base가 이미 정렬이 됬다고 가정한다면 시간복잡도는 O(log n)이 되고 hash map을 활용한 알고리즘은 O(n)이 되므로 이진탐색이 더 좋은 효율을 보여준다.