백준 문제 풀이 - 집합과 맵 단계 - 1269번 대칭 차집합 (실버 4)

이번 문제는 배열이 주어졌을 때, 두 배열의 차집합의 원소 갯수를 구하는 문제이다.

나는 처음에는 HashMap을 이용했는데 가만히 생각해보니 HashSet을 이용해야 했다는 것을 알았다.

우선 구현한 코드를 먼저 보고, 무엇이 잘못 되었고 왜 HashSet을 사용해야 하는지 살펴보자.

---

import java.io.*;
import java.util.*;

class Main{
    public static int n,m;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        HashMap<Long, Boolean> arr = new HashMap<>();
        HashMap<Long, Boolean> arr2 = new HashMap<>();
        str = br.readLine().split(" ");

        for(int i = 0; i < str.length; i++){
            arr.put(Long.parseLong(str[i]), false);
        }

        str = br.readLine().split(" ");
        for(int i = 0; i < str.length; i++){
            arr2.put(Long.parseLong(str[i]), false);
        }

        List<Long> removed = new ArrayList<>();
        Set<Long> keyArr = arr.keySet();
        Long[] temp = keyArr.toArray(new Long[keyArr.size()]);
        for(long l : temp){
            if(arr2.containsKey(l)){
                arr.remove(l);
                arr2.remove(l);
            }
        }


        System.out.println(arr.size() + arr2.size());

    }
}

대충 봐도 쓸데없는 코드가 많이 끼어있는 것이 보인다... 우선 위의 코드도 정상적으로 동작은 한다.
나는 문제를 풀기 위해서 HashMap을 2개 생성하여 각 배열을 집어넣은 후,  첫번째 배열의 Keyset을 Long타입 배열로 복사한다.

그 후 복사된 Long타입 배열을 순회하며 두번째 배열에서 해당 키가 존재하면 첫번째 배열과 두번째 배열에서 해당 값을 remove 한 후 각 배열의 크기를 더하여 출력하도록 설계하였다.

 

---

위 코드에는 문제점이 있는데...

우선, HashMap을 사용할 이유가 없다. 문제는 배열의 요소만 비교하면 되므로 굳이 키-밸류 형태로 사용하는 HashMap을 사용할 필요없이 HashSet을 사용하면 된다. (실제로 위의 코드를 보면 정작 HashMap의 value는 사용하지 않는 것을 볼 수 있다.)

 

두번째로, 굳이 for문을 순회하며 요소를 제거할 필요가 없다. 어차피 차집합의 갯수는 양 배열의 크기에서 겹치는 값만 뺀 값과 같다. HashSet에는 중복값이 존재 할 수 없으므로 입력 단계에서 전체값을 Set에 넣은 후, 각 배열의 합에서 Set의 크기를 빼면 공통된 요소의 수가 나오게 된다. 그 후, 각 배열에서 공통된 요소의 수를 뺀 후, 더하면 그것이 차집합의 갯수이다.

 

예를 들어, {1,2,3}란 A 배열과 {2,3,4,5}란 B 배열이 있다고 생각해 보자.

각 배열의 크기는 3과 4이고, Set의 크기는 {1,2,3,4,5}로 5가 될 것이다. 그러면 3+4-5=2이므로, 각 배열의 공통요소는 2개씩 있다고 계산해 낼 수 있다. 그럼 (3-2) + (4-2)가 되므로 차집합의 크기는 3이 되는데, 실제로 차집합은 {1,4,5}로 3인 것을 확인 할 수 있다. 

 

위의 내용을 생각하며 코드를 바꿔 보았다.

---

import java.io.*;
import java.util.*;

class Main{
    public static int n,m,cnt;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        Set<String> hs = new HashSet<>();
        String[] arr1 = br.readLine().split(" ");
        for(int i = 0; i < arr1.length; i++){
            hs.add(arr1[i]);
        }
        
        String[] arr2 = br.readLine().split(" ");
        for(int i = 0; i < arr2.length; i++){
            hs.add(arr2[i]);
        }
        
        cnt = arr1.length + arr2.length - hs.size();
        System.out.println((arr1.length - cnt) + (arr2.length - cnt));

    }
}

설명한 것 처럼, HashSet hs를 만들어 각 입력 받은 배열의 요소를 모두 넣는다. HashSet에서는 중복값이 존재 할 수 없기 때문에 자동으로 중복이 제거된 값만 hs에 남게된다.

그럼 앞서 설명한 계산식대로 계산만 해주면 굳이 for문을 순회하며 요소를 제거할 필요없이 바로 차집합의 갯수를 계산 해 낼 수 있다.

 

위가 HashSet을 이용한 코드이고, 아래가 HashMap을 이용한 코드이다.

메모리 면에서도 속도면에서도 위의 코드가 훨씬 좋은 효율을 보이는 것을 알 수 있다. (물론 쓸데없이 배열을 선언하고 for문도 하나 더 순회하니 당연한 결과이다.)

그러면 Set에 대해서 잠깐 정리를 하고 넘어가고자 한다.

---

Set 이란...

set은 자바의 Collections의 인터페이스 중 하나로 중복 요소를 포함하지 않는 Collection 이다.

보통 순서가 없는 집합(혹은 목록)을 표현하기 위하여 사용되는데 가장 많이 사용 되는것은 HashSet, TreeSet 및 LinkedHashSet이다.

 

주요 특징들은 다음과 같은데

1. 중복요소가 없다. 동일 요소가 여러 번 추가 되는 경우 한번만 유지 된다.

2. 순서가 없다. Set 인터페이스 자체는 인덱스나 순서가 없기 때문에 TreeSet이나 LinkedHashSet을 이용하여야 한다.

 

구현클래스는 HashSet, TreeSet, LinkedHashSet이 있으며 특징은 다음과 같다.

• HashSet: HashSet은 해시 테이블을 기반으로 하며, 순서 없이 요소를 저장한다. 빠른 검색 속도가 특징
• TreeSet: TreeSet은 이진 검색 트리(레드-블랙 트리)를 기반으로 하며, 요소를 정렬된 순서로 저장한다. 정렬된 순서로 요소를 순회할 때 유용하게 사용할 수 있다..
• LinkedHashSet: LinkedHashSet은 이중 연결 리스트와 해시 테이블을 결합하여 요소를 삽입 순서대로 저장한다. 즉, 입력 순서대로 정렬할 필요가 있는 경우, 사용할 수 있다.

주요 메서드는 여러가지가 있는데

• boolean add(E e): 주어진 요소를 Set에 추가합니다. 만약 요소가 이미 Set에 존재하면 추가하지 않고 false를 반환하며, 추가에 성공하면 true를 반환합니다.
• boolean remove(Object o): 주어진 요소를 Set에서 제거합니다. 요소가 Set에 존재하면 제거하고 true를 반환하며, 없으면 false를 반환합니다.
• void clear(): Set의 모든 요소를 제거하여 비웁니다.int size(): Set에 저장된 요소의 개수를 반환합니다.
• boolean isEmpty(): Set이 비어있는지 여부를 반환합니다. 비어있으면 true, 아니면 false를 반환합니다.
• boolean contains(Object o): 주어진 요소가 Set에 존재하는지 여부를 확인합니다. 존재하면 true, 아니면 false를 반환합니다.
• Iterator<E> iterator(): Set의 요소를 반복하는 데 사용할 수 있는 Iterator를 반환합니다.
• Object[] toArray(): Set의 요소를 배열로 반환합니다.<T> T[] toArray(T[] a): Set의 요소를 특정 유형의 배열로 반환합니다. 주어진 배열의 크기가 충분하지 않으면 새 배열이 생성됩니다.
• boolean containsAll(Collection<?> c): 주어진 컬렉션의 모든 요소가 Set에 포함되어 있는지 여부를 확인합니다. 모든 요소가 포함되면 true, 아니면 false를 반환합니다.
• boolean addAll(Collection<? extends E> c): 주어진 컬렉션의 모든 요소를 Set에 추가합니다. 하나 이상의 요소가 추가되면 true, 아니면 false를 반환합니다.
• boolean removeAll(Collection<?> c): 주어진 컬렉션의 모든 요소를 Set에서 제거합니다. 하나 이상의 요소가 제거되면 true, 아니면 false를 반환합니다.
• boolean retainAll(Collection<?> c): 주어진 컬렉션과 교집합을 구해 Set에 유지합니다. Set이 변경되면 true, 아니면 false를 반환합니다.
• boolean equals(Object o): 주어진 객체와 Set이 동등한지 여부를 확인합니다. 객체가 동등하면 true, 아니면 false를 반환합니다.
• int hashCode(): Set의 해시 코드를 반환합니다

 

따라서 Set은 주로 고유한 값을 저장하여 집합 연산(교집합, 차집합, 합집합 등...)을 수행하는데 자주 사용 된다.