2개 리스트의 교집합, 합집합, 차집합 구하기

교집합

retainAll() 메서드로 두 리스트의 교집합 구하기

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        Set<String> str1Set = new HashSet<>(Arrays.asList("ab", "bc", "cd", "ef", "fg"));
        Set<String> str2Set = new HashSet<>(Arrays.asList("cd", "ef", "fg", "gh", "hi"));

        Set<String> intersection = new HashSet<>(str1Set);
        intersection.retainAll(str2Set);

        // Set to List
        List<String> intersectionList = new ArrayList<>(intersection);

        System.out.println("HashSet + retainAll() 이용 : " + intersectionList);
    }
}

 

Stream을 이용해 두 리스트의 교집합 구하기

import java.util.List;
import java.util.Arrays;
import java.util.function.Predicate;
import java.util.stream.Collectors;

public class Test {
    public static void main(String[] args) {
        List<String> str1List = Arrays.asList("ab", "bc", "cd", "ef", "fg");
        List<String> str2List = Arrays.asList("cd", "ef", "fg", "gh", "hi");

        List<String> intersection = str1List.stream()
                .filter(el -> str2List.stream().anyMatch(Predicate.isEqual(el)))
                .collect(Collectors.toList());

        System.out.println("List + Stream 이용 = " + intersection);
    }
}

 

for문을 통해 직접 순회하면서 두 리스트의 교집합 구하기

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        List<String> str1List = Arrays.asList("ab", "bc", "cd", "ef", "fg");
        List<String> str2List = Arrays.asList("cd", "ef", "fg", "gh", "hi");

        List<String> copyOfStr2List = new ArrayList<>(str2List);

        List<String> intersection = new ArrayList<>();

        for (String str1 : str1List) {
            for (int j = 0; j < copyOfStr2List.size(); j++) {
                if (str1.equals(copyOfStr2List.get(j))) {
                    intersection.add(copyOfStr2List.get(j));
                    copyOfStr2List.remove(j);
                    break;
                }
            }
        }

        System.out.println("for문으로 직접 순회 = " + intersectionList2);
    }
}

str1List를 기준으로 직접 순회하며 공통되는 요소들을 찾습니다.

str2List의 복사본 리스트를 만들고 공통되는 요소를 지워주면서 찾는 방법입니다.

 

 

교집합 코드 결과값

 

합집합

addAll() 메서드로 두 리스트의 교집합 구하기

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        Set<String> str1Set = new HashSet<>(Arrays.asList("ab", "bc", "cd", "ef", "fg"));
        Set<String> str2Set = new HashSet<>(Arrays.asList("cd", "ef", "fg", "gh", "hi"));

        Set<String> union = new HashSet<>(str1Set);
        union.addAll(str2Set);

        // Set to List
        List<String> unionList = new ArrayList<>(union);

        System.out.println("HashSet + addAll() 이용 : " + union);
    }
}

 

for문을 통해 직접 순회하면서 두 리스트의 합집합 구하기

import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<String> str1List = Arrays.asList("ab", "bc", "cd", "ef", "fg");
        List<String> str2List = Arrays.asList("cd", "ef", "fg", "gh", "hi");
        
        List<String> unionList = new ArrayList<>();
        unionList.addAll(str1List);
        unionList.addAll(str2List);
        
        List<String> intersectionList = Arrays.asList("cd", "ef", "fg");

        for (String intersection : intersectionList) {
            for (int j = 0; j < unionList.size(); j++) {
                if (intersection.equals(unionList.get(j))) {
                    unionList.remove(j);
                    break;
                }
            }
        }

        System.out.println("for문으로 직접 순회 : " + union);
    }
}

이 방법은 먼저 교집합을 구한 후, 적용할 수 있는 방법입니다.

addAll() 메서드를 통해, 두 리스트를 모두 넣어줍니다.

그리고, for문을 직접 순회하면서 교집합의 요소들을 빼주는 형태입니다.

*합집합 = (A 집합 + B 집합 - A와 B의 교집합)

 

 

합집합 코드 결과값

 

차집합

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        Set<String> str1Set = new HashSet<>(Arrays.asList("ab", "bc", "cd", "ef", "fg"));
        Set<String> str2Set = new HashSet<>(Arrays.asList("cd", "ef", "fg", "gh", "hi"));

        Set<String> subtract = new HashSet<>(str1Set);
        subtract.removeAll(str2Set);

        // Set to List
        List<String> subtractList = new ArrayList<>(subtract);

        System.out.println("HashSet + removeAll() 이용 : " + subtractList);
    }
}

 

 

차집합 코드 결과값

코드가 List와 Set으로 혼합되어 있습니다.

서로 변환해서 잘 사용하면 되지만, Set은 중복값을 가지지 않기 때문에, List의 방법과는 조심해서 사용해야할 부분이 있습니다.

이렇게 혼합해서 기술한 부분은 여러 블로그를 참고하고 덧붙여 적은 것이기 때문에 그렇습니다.

 

 

이번에 교집합, 합집합, 그리고 차집합을 구하는 내용을 블로깅하게 된 이유는

프로그래머스 뉴스 클러스터링 문제를 풀 때, 많은 방식으로 구할 수 있다는 걸 알고 정리해두기 위함입니다.

 

이 문제를 풀 때, 필요한 부분은 교집합과 합집합 내용들입니다.

위에서 기술한 교집합, 합집합 구하는 코드들이 모두 적용되는 것은 아닙니다.

다양한 방법들을 조합해봤지만, 몇몇 테스트케이스에서 통과되지 않았습니다.

 

결국, 이 문제를 해결하는데 해답으로 제출했던 교집합과 합집합 코드는 맨 마지막에 기술한

for문을 직접 순회해서 찾는 코드였습니다.

왜 굳이 for문을 돌려서 보기에도 좋지 않은 코드를 기술해놨을까 했을 겁니다.

 

여러 블로그에서 소개하는 교집합, 합집합을 구하는 코드로는 도저히 문제가 풀리지 않았고

for문으로 순회해서 구하는 방법을 직접 구현하고 적용했더니 문제가 풀렸습니다.

 

어떤 블로그를 참고해도 문제가 풀리지 않을 경우, 해당 코드를 참고해보시길 바랍니다.

 

    // 교집합 구하기
    private List<String> makeIntersectionList(List<String> str1List, List<String> str2List) {
        List<String> intersectionList = new ArrayList<>();
        List<String> copyOfStr2List = new ArrayList<>(str2List);

        for (String str1 : str1List) {
            for (int j = 0; j < copyOfStr2List.size(); j++) {
                if (str1.equals(copyOfStr2List.get(j))) {
                    intersectionList.add(copyOfStr2List.get(j));
                    copyOfStr2List.remove(j);
                    break;
                }
            }
        }

        return intersectionList;
    }


    // 합집합 구하기
    private List<String> makeUnionList(List<String> str1List, List<String> str2List, List<String> intersectionList) {
        List<String> unionList = new ArrayList<>();
        unionList.addAll(str1List);
        unionList.addAll(str2List);

        for (String intersection : intersectionList) {
            for (int j = 0; j < unionList.size(); j++) {
                if (intersection.equals(unionList.get(j))) {
                    unionList.remove(j);
                    break;
                }
            }
        }

        return unionList;
    }

코드 소스 : https://github.com/bangjaeyoung/codingtest/blob/main/programmers/level2/Sol_17677.java

 

 

정답은 아니니, 참고해서 풀어주시길 바랍니다.

잘못된 부분이나 보충해야할 부분은 언제든 지적 부탁드립니다.