[백준] 1822번 : 차집합 – JAVA [자바]

https://www.acmicpc.net/problem/1822

1822번: 차집합

 

 

---

• 문제

 

 

---

• 문제 풀이

 

백준 1822번 차집합은 실버 4 난이도의 해시 및 정렬 문제이다. 

 

이 문제에서는 집합 A의 원소의 개수 N개와 집합 B의 원소의 개수 M개가 주어진다. 이때 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수와 이 원소들을 오름차순으로 정렬해서 출력을 하면 된다. 

 

이 문제에서는 집합 A에 있는 원소들이 먼저 주어지고 그다음에 집합 B에 있는 원소들이 주어진다. 하지만, 집합 A에 있는 원소들을 먼저 StringTokenizer로만 읽고 집합 B에 있는 원소들을 먼저 HashSet에 저장하면 쉽게 풀 수 있다. 

 

그리고 집합 A에 있는 원소들을 StringTokenizer로만 읽었으니 이 StringTokenizer에 있는 숫자들을 처리하면 된다. 이 숫자들을 읽을 때 HashSet에 있는지 확인하고 없으면 리스트에 넣어주면 된다. 그리고 마지막에 리스트를 정렬해서 이 리스트의 크기와 이 리스트에 있는 원소들을 출력해 주면 된다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 입력받는 숫자의 개수 정보는 필요하지 않으므로 버림
        br.readLine();
        
        // Set은 중복을 허용하지 않는 자료구조로, 집합 B의 원소들을 저장하기 위해 사용
        Set<Integer> set = new HashSet<>();
        
        // 집합 B의 원소들을 저장하는 리스트
        List<Integer> list = new ArrayList<>();
        
        // 집합 B의 원소들을 입력받고, Set에 추가
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            set.add(num);
        }
        
        // 집합 A의 원소들을 입력받고, 집합 B에 포함되지 않는 경우 리스트에 추가
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        while (st2.hasMoreTokens()) {
            int num = Integer.parseInt(st2.nextToken());
            if (!set.contains(num)) list.add(num);
        }
        
        // 리스트의 크기를 출력하여 집합 A에 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력
        System.out.println(list.size());
        
        // 리스트가 비어있지 않다면, 리스트를 오름차순으로 정렬하여 출력
        if (list.size() != 0) {
            Collections.sort(list);
            StringBuilder sb = new StringBuilder();
            for (int i : list) {
                sb.append(i + " ");
            }
            System.out.println(sb);
        }
    }
}