[JAVA] 백준 1822번 : 차집합

[1822번 : 차집합] - Silver4

---

[ 문제 ]

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

---

[ 입력 ]

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다.

둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다.

하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

---

[ 출력 ]

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다.

다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다.

집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

# 예제 입력 1
4 3
2 5 11 7
9 7 4

# 예제 출력 1
3
2 5 11

# 예제 입력 2
3 5
2 5 4
1 2 3 4 5

# 예제 출력 2
0

---

[ Code ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int aSize = Integer.parseInt(st.nextToken());
        int bSize = Integer.parseInt(st.nextToken());

        HashMap<Integer, Integer> aMap = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < aSize; i++) {
            aMap.put(Integer.parseInt(st.nextToken()), 1);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < bSize; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (aMap.containsKey(num)) {
                aMap.put(num, 0);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i : aMap.keySet()) {
            if (aMap.get(i) == 1) {
                list.add(i);
            }
        }

        if (list.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(list.size());
            Collections.sort(list);
            for (int i : list) {
                System.out.print(i + " ");
            }
        }
    }
}

- 집합 A의 값을 해시 맵에 추가한다.

- 집합 B의 값이 들어오면 해시 맵에 존재하는 값인지 확인하고, 존재한다면 value의 값을 0으로 바꾼다.

- value가 0인 값의 키를 찾아서 List에 넣는다.

- 리스트 정렬 후 출력한다.